Efficient Parallel Algorithms for Testingkand Finding Disjoints-tPaths in Graphs

DOI10.1137/0220022MaRDI QIDQ3210185zbMATHOpenAlexFDO

Authors Samir Khuller, Baruch Schieber

Publication date 1991

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220022

zbMATH Keywords

parallel algorithmdisjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Paths and cycles (05C38) Connectivity (05C40)

Recommendations

• A faster parallel algorithm for k-connectivity
• Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
• Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• Parallel algorithms for connectivity problems in graph theory

Cited in

(8)

• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks
• A faster parallel algorithm for \(k\)-connectivity
• Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
• Flow in planar graphs with vertex capacities
• Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
• Walking through waypoints
• Efficient algorithms for listing \(k\) disjoint \(st\)-paths in graphs

This page was built for publication: Efficient Parallel Algorithms for Testingkand Finding Disjoints-tPaths in Graphs

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