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

DOI10.1016/S0020-0190(98)00195-1MaRDI QIDQ294620zbMATH OpenOpenAlexFDO

Authors Chin-Wen Ho, Jou-Ming Chang

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

chordal bipartite graphsgraph algorithmsshortest pathsstrongly chordal graphs

Mathematics Subject Classification ID

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

Recommendations

• All-pairs-shortest-length on strongly chordal graphs
• All pairs shortest paths for graphs with small integer length edges
• Unified all-pairs shortest path algorithms in the chordal hierarchy
• scientific article; zbMATH DE number 913360
• Solving the shortest-paths problem on bipartite permutation graphs efficiently

Cites work

• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• All-pairs-shortest-length on strongly chordal graphs
• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• Characterizations of strongly chordal graphs
• Doubly lexical ordering of dense 0--1 matrices
• Doubly Lexical Orderings of Matrices
• Efficient Algorithms for Shortest Paths in Sparse Networks
• scientific article; zbMATH DE number 512919 (Why is no real title available?)
• scientific article; zbMATH DE number 913360 (Why is no real title available?)
• Incidence matrices and interval graphs
• Matrix multiplication via arithmetic progressions
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Solving the shortest-paths problem on bipartite permutation graphs efficiently
• Three Partition Refinement Algorithms
• Totally-Balanced and Greedy Matrices

Cited in

(7)

• Some optimization problems on weak-bisplit graphs
• Unified all-pairs shortest path algorithms in the chordal hierarchy
• All-pairs-shortest-length on strongly chordal graphs
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• An all-pairs shortest path algorithm for bipartite graphs
• Computing the all-pairs longest chains in the plane
• \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs

Describes a project that uses

Uses Software

• Algorithm 97

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294620)