CSCE 5170: Graph Theory - Spring 2011
Instructor: Paul Tarau,
Associate Professor - see my home page
for contact info and office hours
E-mail : t a r a u@cs.unt.edu
WWW : http://www.cs.unt.edu/~tarau
Address: Department
of Computer Science, University of North Texas,
P.O. Box 311366, Denton,
Texas 76203, USA
Phone : Tel : +1-940-565-2806, +1-940-565-2767
Fax : +1-940-565-2799
Description and Objectives:
An advanced course, with focus on computational and
algorithmic aspects of Graph Theory and applications to web and social network
analysis, natural language processing, data-mining, logic and circuits etc.
Syllabus
- Basic
Definitions
- Graph,
Digraphs, DAGs,Trees, Multigraphs, Hypergraphs, Finite Categories
- Binary
Relations, Boolean Matrices
- Packages
and Tools for Graph Manipulation
- Inductive
Graphs in Haskell
- Graphs
in Mathematica
- The
Boost C/C++ Graph Library
- Building
a Java Based Graph Package
- Graph
Representations
- Data
Structures and Bounds on Graph Operations
- Representing
Digraphs / Multi-Graphs / Finite Categories
- Encodings
and Succinct Graph and Tree Representations
- A
Selection of Theorems and Proof Techniques
- A
Selection of Graph Algorithms
- Overview
of Fundamental Algorithms
- Graph
Visitor Algorithms, BFS, DFS
- Dijkstra’s,
Bellman-Ford, Warshall’s algorithms
- Transitive
Closure/Transitive Reduction
- Strong
Components, linear time 2-SAT solving
- Graph
and Subgraph Isomorphism
- Kernels
and Dominators
- Graph
Coloring
- Hamiltonian
Circuits
- Circuit
Synthesis
- Flow
in Networks
- Constraint
Propagation
- The
“PageRank family” of graph ranking algorithms
- 2D and
3D Graph visualization
- Applications
of Graph Theory to:
- Natural
Language Processing
- Compilation
of Programming Languages – Register Allocation
- Memory
Management of Runtime Systems
- Circuit
Design
- Social
Network Analysis
- Datamining
- Knowledge
Representation
- Software
Engineering
- Other
graph theory related topics based
on students’ interests
Prerequisites: good
mathematical background, some experience with a functional programming
language,
some background
in Algorithm Analysis, Complexity Theory and Theoretical Computer Science
Evaluation:
- Team
research paper presentations: 20%
- Team
coding projects 40%
- Individual
Exam: 40%
Assignment
1. Due Feb 22 at noon. Compute the transitive closure and a transitive
reduction of a randomly generated a) digraph, b) DAG. Use either Mathematica or
the Java based graph package discussed in class. See this paper for a possible algorithm:
http://epubs.siam.org/sicomp/resource/1/smjcat/v1/i2/p131_s1.
Assignment
2: Due March 15, at noon. Implement a graph-based linear time 2-SAT solver. Use
either Mathematica or the Java based graph package discussed in class. The
2-SAT problem is given in DIMACS format i.e. as a file containing a list of
literals represented as integers marked with + or – and separated with 0 to
mark the end of clauses. To compute the strong components, you can use
Kosaraju, Gabow or Tarjan’s algorithms.
Assignment
3: Due Thursday April 7, at noon. Implement using our Java-based graph
package or this alternative graph
package, a 2D graph layout algorithm that allows interactive exploration of
a directed graph, possibly with zoom-in/zoom-out and/or hyperbolic geometry
(fish-eye) views. Test your layout algorithm using random digraphs and attach
to your submission images obtained on at least 5 random digraphs of various
sizes.