Name
Abstract | ||
|---|---|---|
The objective of this paper is to advance the view that solving the all-pairs shortest path (APSP) problem for a chordal graph G is a two-step process: the first step is determining vertex pairs at distance two (i.e., computing G 2 ) and the second step is finding the vertex pairs at distance three or more. The main technical result here is that the APSP problem for a chordal graph can be solved in O ( n 2 ) time (optimally), if G 2 is already known. It can be shown that computing G 2 for chordal graphs is as hard as for general graphs. We then show certain subclasses of chordal graphs for which G 2 can be computed more efficiently. This leads to optimal APSP algorithms for these classes of graphs in a more natural way than previously known results. Finally, we present an optimal parallel algorithm for the APSP problem on chordal graphs by exploiting new structural properties of shortest paths. Our parallel algorithm uses O ( M ( n )) operations where M ( n ) is the time needed for the fastest known algorithm for multiplying two n × n matrices over a ring. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0166-218X(96)00103-5 | Discrete Applied Mathematics |
Keywords | Field | DocType |
shortest path algorithm,unified all-pairs,chordal hierarchy,shortest path,chordal graph,all pairs shortest path,parallel algorithm | Graph theory,Discrete mathematics,Combinatorics,Indifference graph,Interval graph,Shortest path problem,Vertex (geometry),Chordal graph,Algorithm,Treewidth,Pathwidth,Mathematics | Journal |
Volume | Issue | ISSN |
77 | 1 | Discrete Applied Mathematics |
Citations | PageRank | References |
6 | 0.52 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| K. Han | 1 | 6 | 0.52 |
| Chandra N. Sekharan | 2 | 105 | 12.77 |
| R. Sridhar | 3 | 6 | 0.52 |