Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph

DOI10.1137/0221032zbMath0761.68074OpenAlexW2011245187MaRDI QIDQ4016910

Vijay V. Vazirani, Samir Khuller, Stephen G. Mitchell

Publication date: 16 January 1993

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

Full work available at URL: https://hdl.handle.net/1813/6876

zbMATH Keywords

parallel algorithmdisjoint pathsKuratowski homeomorph

Mathematics Subject Classification ID

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

Related Items (6)

The parallel complexity of tree embedding problems (extended abstract) ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Improved Algorithms for the 2-Vertex Disjoint Paths Problem ⋮ Unnamed Item ⋮ Walking through waypoints ⋮ Structure and recognition of graphs with no 6-wheel subdivision

This page was built for publication: Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph