Solving the all-pairs-shortest-length problem on chordal bipartite graphs

Chin Wen Ho, Jou Ming Chang

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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.

Original languageEnglish
Pages (from-to)87-93
Number of pages7
JournalInformation Processing Letters
Volume69
Issue number2
DOIs
StatePublished - 29 Jan 1999

Keywords

  • Algorithms
  • Chordal bipartite graphs
  • Shortest paths
  • Strongly chordal graphs

Fingerprint

Dive into the research topics of 'Solving the all-pairs-shortest-length problem on chordal bipartite graphs'. Together they form a unique fingerprint.

Cite this