@article{798724b44dbb41c7916430a3bf92d661,
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 paths between 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 be transformed to solving the same problem on certain strongly chordal graphs. Consequently, there is an O(n2) time-optimal algorithm for this problem.",
keywords = "Algorithms, Chordal bipartite graphs, Shortest paths, Strongly chordal graphs",
author = "Ho, {Chin Wen} and Chang, {Jou Ming}",
note = "Funding Information: “This work was partially supported by the National Science Council of Taiwan under grant NSC87-2213-E-008-017. We would like to thank the anonymous referees for helping us improve the presentation of this paper. * Corresponding author. Email: hocw@csie.ncu.edu.tw.",
year = "1999",
month = jan,
day = "29",
doi = "10.1016/s0020-0190(98)00195-1",
language = "???core.languages.en_GB???",
volume = "69",
pages = "87--93",
journal = "Information Processing Letters",
issn = "0020-0190",
number = "2",
}