Solving the shortest-paths problem on bipartite permutation graphs efficiently

DOI10.1016/0020-0190(95)00084-PMaRDI QIDQ672656zbMATH OpenFDO

Authors Lin Chen

Publication date 28 February 1997

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

Full work available at URL https://doi.org/10.1016/0020-0190(95)00084-P

zbMATH Keywords

Bipartite permutation graphsParallel algorithmsShortest pathsUpper and lower bounds

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• Optimal computation of shortest paths on doubly convex bipartite graphs
• Efficient parallel algorithms for permutation graphs

Cites work

• A new upper bound on the complexity of the all pairs shortest path problem
• A note on two problems in connexion with graphs
• A Theorem on Boolean Matrices
• An Efficient Parallel Biconnectivity Algorithm
• APPLICATION OF BROADCASTING WITH SELECTIVE REDUCTION TO THE MAXIMAL SUM SUBSEGMENT PROBLEM
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Bipartite permutation graphs
• Efficient parallel algorithms for bipartite permutation graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 4155887 (Why is no real title available?)
• Optimal parallel time bounds for the maximum clique problem on intervals
• Parallel Matrix and Graph Algorithms
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(10)

• Some optimization problems on weak-bisplit graphs
• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• Optimal computation of shortest paths on doubly convex bipartite graphs
• Solving the all-pairs-shortest-length problem on chordal bipartite graphs
• Core and Conditional Core Path of Specified Length in Special Classes of Graphs
• Methods of local optimization for the problem of permutating bipartite graphs
• An all-pairs shortest path algorithm for bipartite graphs
• A linear algorithms for the two paths problem on permutation graphs
• On the complexity of the maximum biplanar subgraph problem
• \(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 shortest-paths problem on bipartite permutation graphs efficiently

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