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 attendancebased.
Tentative schedule of topics:
 Week I. Organizational meeting; survey of textbook shortest path
algorithms. BFS, Depthfirst iterative deepening, Dijkstra,
BellmanFord, FloydWarshall.
 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
[Goldberg,
SICOMP 1995]; k shortest paths [Eppstein, SICOMP 1998].
 Week VI. Dynamic allpairs shortest paths [Demetrescu and Italiano, JACM 2004; Thorup, STOC 2005]; Distance oracles [Thorup and Zwick, JACM 2005]
 Week VII. Graphs defined by distances: Distancehereditary
graphs. Recognition, characterization, and confluent drawing.
 Week VIII. Partial cubes: definition and characterization. Bound on
number of edges; quadratictime shortest path algorithm and recognition.
 Week IX. NO CLASS MONDAY (Memorial Day holiday). Lattice dimension of
partial cubes.
 Week X. Median graphs and squaregraphs.
Syllabus from Spring 2007: Geometric Graph Theory