Distances in graphs and graphs defined by distances
David Eppstein, Computer Science 295, Spring 2008
The course will meet Monday and Wednesdays, 1:00 - 1:50, in CS
243. Grading will be attendance-based.
Tentative schedule of topics:
- Week I. Organizational meeting; survey of textbook shortest path
algorithms. BFS, Depth-first iterative deepening, Dijkstra,
- Week II. Fast matrix multiplication. Unweighted undirected shortest
paths using matrix multiplication [Seidel, STOC 1992]; Subcubic algorithms for all pairs shortest
paths with small integer weights [Zwick, JACM 2002].
- Week III. Combinatorial algorithms for integer weights. Undirected
integer weight shortest paths in linear time [Thorup, JACM 1999]. Unweighted shortest paths with small additive error in subcubic
time, not based on matrix multiplication [Aingworth et al, SICOMP 1999].
- Week IV. Parametric shortest paths [Gusfield; Carstenson; Young et al.; Eppstein, SICOMP
2003; Eppstein and Wortman].
- Week V. Faster negative cycle detection by scaling
SICOMP 1995]; k shortest paths [Eppstein, SICOMP 1998].
- Week VI. Dynamic all-pairs shortest paths [Demetrescu and Italiano, JACM 2004; Thorup, STOC 2005]; Distance oracles [Thorup and Zwick, JACM 2005]
- Week VII. Graphs defined by distances: Distance-hereditary
graphs. Recognition, characterization, and confluent drawing.
- Week VIII. Partial cubes: definition and characterization. Bound on
number of edges; quadratic-time shortest path algorithm and recognition.
- Week IX. NO CLASS MONDAY (Memorial Day holiday). Lattice dimension of
- Week X. Median graphs and squaregraphs.
Syllabus from Spring 2007: Geometric Graph Theory