Unified all-pairs shortest path algorithms in the chordal hierarchy (Q1364781): Difference between revisions

The authors show that solving the all-pairs shortest path (APSP) problem for a chordal graph \(G\) is a two-step process: (1) Compute \(G^2\). (2) Find the vertex pairs of distance three or more. The main result is that knowing \(G^2\), the APSP problem for chordal graphs can be solved in \(O(n^2)\) time (optimal time). Parallel algorithms are also considered.