Optimal parallel algorithms for path problems on planar graphs

DOI10.1016/0304-3975(94)00189-PMaRDI QIDQ673083zbMATHOpenAlexFDO

Authors G. Srikrishna, C. Pandu Rangan

Publication date 28 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(94)00189-p

zbMATH Keywords

all-bidirectional-edgesbiconnected planar graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• A linear algorithm for the all-bidirectional-edges problem on planar graphs
• A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs
• Optimal parallel algorithms on planar graphs
• A linear-time algorithm for edge-disjoint paths in planar graphs
• Publication:3795245

Cites work

• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 4060742 (Why is no real title available?)
• scientific article; zbMATH DE number 4064468 (Why is no real title available?)
• scientific article; zbMATH DE number 3725714 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• A Polynomial Solution to the Undirected Two Paths Problem
• A linear algorithm for the all-bidirectional-edges problem on planar graphs
• An Efficient Parallel Biconnectivity Algorithm
• Disjoint paths in graphs
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• On the Computational Complexity of Combinatorial Problems
• Optimal parallel algorithm for finding \(st\)-ambitus of a planar biconnected graph
• Parallel Prefix Computation
• The directed subgraph homeomorphism problem
• Towards optimal parallel bucket sorting

Cited in

(8)

• A linear algorithm for the all-bidirectional-edges problem on planar graphs
• On the complexity of optimal parallel cooperative path-finding
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• A simple parallel algorithm for the single-source shortest path problem on planar digraphs
• Parallel complexity of computing a maximal set of disjoint paths
• Optimal parallel algorithm for finding \(st\)-ambitus of a planar biconnected graph
• Notes on 'divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model'
• Bidirectional edges problem. I: A simple algorithm

This page was built for publication: Optimal parallel algorithms for path problems on planar graphs

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