Unified all-pairs shortest path algorithms in the chordal hierarchy (Q1364781)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Unified all-pairs shortest path algorithms in the chordal hierarchy |
scientific article |
Statements
Unified all-pairs shortest path algorithms in the chordal hierarchy (English)
0 references
28 August 1997
0 references
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.
0 references
all-pairs shortest path
0 references
chordal graph
0 references
algorithms
0 references
0 references
