Solving the shortest-paths problem on bipartite permutation graphs efficiently

DOI10.1016/0020-0190(95)00084-PzbMath0875.68502MaRDI QIDQ672656

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)

Related Items

Solving the all-pairs-shortest-length problem on chordal bipartite graphs, \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs, Optimal computation of shortest paths on doubly convex bipartite graphs, An all-pairs shortest path algorithm for bipartite graphs, On the complexity of the maximum biplanar subgraph problem, Core and Conditional Core Path of Specified Length in Special Classes of Graphs, Some optimization problems on weak-bisplit graphs

Uses Software

• Algorithm 97

Cites Work

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