| L05 | Nov. 15 | [+] Multiple Source Shortest Paths |
[Notes] | [Video] |
|---|---|---|---|---|
| We develop an O(n log n)-time algorithm that, given a shortest path tree rooted at some vertex r of a face f in a directed planar graph, computes a representation of all shortest path trees rooted at all vertices of f. This representation can be used to report distances between any vertex of f and any other vertex in the graph in O(log n) time. The algorithm is based on interdigitating trees and uses dynamic trees to represent the trees efficiently. | ||||
| L06 | Nov. 22 | [+] Shortest Paths with Negative Lengths |
[Notes] | [Video] |
| We start with a recap of the MSSP algorithm and discuss how the data structure can be used to report shortest paths and distances. The bulk of this lecture is devoted to a nearly-linear time algorithm for shortest paths in the presence of negative lengths. The heart of the algorithm is a procedure to implement the Bellman-Ford algorithm on the dense distance graph - the complete graph on vertices of a cycle separator, where the length of an edge in the DDG corresponds to the length of a shortest path between its endpoints in the underlying planar graph. We show that implementing an iteration of Bellman-Ford can be cast into the problem of finding all column minima in the weighted incidence matrix of the DDG. We then introduce the Monge property, and show that we can find all column minima of a Monge matrix in time that is nearly linear in the number of rows. Finally we show that the weighted incidence matrix of the DDG can be decomposed into a small number of Monge matrices. | ||||
| L07 | Nov. 29 | [+] Shortest Paths in Dense Distance Graphs |
[Notes] | [Video] |
| This lecture begins with a brief discussion of the incision technique, and of r-divisions. The main topic of this lecture is an implementation of Dijkstra's algorithm on dense distance graphs, due to Fakcharoenphol and Rao. The running time is nearly linear in the number of vertices of the DDG, rather than in the number of edges as in a naive implementation of Dijkstra's algorithm. | ||||
| L08 | Dec. 6 | [+] Exact Distance Oracles and Branchwidth |
[Notes] | [Video] |
|
We conclude the discussion of FR-Dijkstra and go into a relatively
short discussion of exact distance oracles for planar graphs. We
apply MSSP and FR-Dikstra to obtain a data stucture with nearly linear space and
preprocessing time, that can answer distance queries in roughly
√n time. We then move on to a new topic - approximation schemes, and discuss carving and branch decompositions. | ||||
| L09 | Dec. 13 | [+] Branchwidth and Baker's approximation technique |
[Notes] | [Video] |
| We redefine branchwidth and review how to solve vertex cover using a dynamic program on the branch decomposition. Given a planar graph, we show how to find a carving decomposition whose width is related to the radius of the dual graph. We use this to prove Tamaki's theorem which shows (algorithmically) the existence of a branch decomposition whose width is roughly twice the minimum between the primal and dual radii. We discuss Baker's approximation technique which breaks a planar graph into subgraphs induced by vertices at a constant number of consecutive BFS levels. By Tamaki's theorem each subgraph has constant branchwidth, so can be solved optimally using DP. The optimal solutions from all subgraph are combined to give a near-optimal solution in the entire graph. | ||||
| L10 | Dec. 20 | [+] EPTAS for the travelling salseman problem |
[Notes] | [Video] |
| We describe an efficient PTAS for the travelling salesman problem in undirected planar graphs. | ||||
| L11 | Dec. 27 | [+] Circulations and maximum flow in st-planar graphs |
[Notes] | [Video] |
| We start our treatment of flow in planar graphs by relating circulations in the primal graph with face potentials in the planar dual. We show that the residual capacity of a dart with respect to a primal circulations is the slack cost of that dart in the dual with respect to the corresponding potential function. This establishes a connection between distances in the planar dual and capacity respecting circulations in the primal. We use this relation to give a linear-time algorithm for maximum st-flow when the source and sink lie on the same face. | ||||
| L12 | Jan. 3 | [+] Maximum st-flow in directed planar graphs |
[Notes] | [Video] |
| We describe an O(nlog n)-time algorithm for finding a maximum st-flow in directed planar graphs. The algorithm, due to Borradaile and Klein, resembles the MSSP algorithm, with the roles of primal and dual swapped. It maintains a dual shortest path tree as the (value of the) flow is increased, until a cycle is introduced into the dual tree, which corresponds to a saturated st-cut in the primal. Most of the lecture is devoted to analyzing the number of pivots performed by the algorithm. We present the analysis of Erickson, which uses a universal cover of the dual graph to show that each dart is ejected from the dual tree at most once. | ||||
| L13 | Jan. 10 | [+] Maximum flow in planar graphs with multiple sources and sinks |
[Notes] | [Video] |
| We discuss how to find a maximum flow in a planar flow network with multiple sources and sinks. We introduce pseudoflows and define a sense in which a pseudoflow is maximum. The heart of the lecture is a procedure for eliminating residual paths between vertices with positive and negative inflow on a cycle, which is used by a recursive algorithm for the maximum flow problem. | ||||