Paper Info
Title
Solving the all-pairs-shortest-length problem on chordal bipartite graphs
Abstract
The all-pairs-shortest-length (APSL) problem of a graph is to find the lengths of the shortest pathsbetween all pairs of vertices. In this paper, we study the APSL problem on chordal bipartite graphs.By a simple reduction, we show that solving the APSL problem on chordal bipartite graphs can betransformed to solving the same problem on certain strongly chordal graphs. Consequently, there isan O(n2) time-optimal algorithm for this problem.Keywords: shortest paths, chordal bipartite...
Year
DOI
Venue
1999
10.1016/S0020-0190(98)00195-1
Inf. Process. Lett.
Keywords
Field
DocType
chordal bipartite graph,all-pairs-shortest-length problem,shortest path,algorithms,bipartite graph
Graph theory,Graph,Discrete mathematics,Indifference graph,Combinatorics,Shortest path problem,Vertex (geometry),Vertex (graph theory),Bipartite graph,Chordal graph,Mathematics
Journal
Volume
Issue
ISSN
69
2
0020-0190
Citations 
PageRank 
References 
5
0.46
14
Authors
2
Name
Order
Citations
PageRank
Chin-Wen Ho157339.27
Jou-Ming Chang254650.92