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)

zbMATH Keywords

Parallel algorithmsUpper and lower boundsShortest pathsBipartite permutation graphs

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

• scientific article; zbMATH DE number 4155887 (Why is no real title available?)
• A Theorem on Boolean Matrices
• A new upper bound on the complexity of the all pairs shortest path problem
• A note on two problems in connexion with graphs
• APPLICATION OF BROADCASTING WITH SELECTIVE REDUCTION TO THE MAXIMAL SUM SUBSEGMENT PROBLEM
• An Efficient Parallel Biconnectivity Algorithm
• 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
• 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)

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