Solving the shortest-paths problem on bipartite permutation graphs efficiently
From MaRDI portal
Publication:672656
DOI10.1016/0020-0190(95)00084-PzbMath0875.68502MaRDI QIDQ672656
Publication date: 28 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items (7)
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
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
This page was built for publication: Solving the shortest-paths problem on bipartite permutation graphs efficiently
