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, Bellman-Ford, Floyd-Warshall.
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 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 partial cubes.
Week X. Median graphs and squaregraphs.