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

DOI10.1016/S0020-0190(98)00195-1zbMath1339.05205OpenAlexW2135039026MaRDI QIDQ294620

Jou-Ming Chang, Chin-Wen Ho

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001951?np=y

zbMATH Keywords

shortest pathsgraph algorithmschordal bipartite graphsstrongly chordal graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

\(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs ⋮ An all-pairs shortest path algorithm for bipartite graphs ⋮ Some optimization problems on weak-bisplit graphs

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Solving the shortest-paths problem on bipartite permutation graphs efficiently
• Matrix multiplication via arithmetic progressions
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Characterizations of strongly chordal graphs
• All-pairs-shortest-length on strongly chordal graphs
• Doubly lexical ordering of dense 0--1 matrices
• Incidence matrices and interval graphs
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• Three Partition Refinement Algorithms
• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• Efficient Algorithms for Shortest Paths in Sparse Networks

This page was built for publication: Solving the all-pairs-shortest-length problem on chordal bipartite graphs