Unified all-pairs shortest path algorithms in the chordal hierarchy (Q1364781)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Unified all-pairs shortest path algorithms in the chordal hierarchy |
scientific article; zbMATH DE number 1053466
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Unified all-pairs shortest path algorithms in the chordal hierarchy |
scientific article; zbMATH DE number 1053466 |
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
