An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm

DOI10.1016/0020-0190(89)90064-1MaRDI QIDQ1124337zbMATH OpenOpenAlexFDO

Authors Kazuo Iwano

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90064-1

zbMATH Keywords

parallel algorithmdepth-first searchmaximal paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Paths and cycles (05C38)

Recommendations

• A parallel algorithm for the maximal path problem
• Parallel complexity of computing a maximal set of disjoint paths
• Parallelism and the maximal path problem
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Fast parallel graph searching with applications

Cites work

• A random NC algorithm for depth first search
• An O(n2log n) parallel max-flow algorithm
• An improved parallel algorithm for maximal matching
• Parallelism in random access machines

Cited in

(6)

• A parallel algorithm for the maximal path problem
• Improved approximation for node-disjoint paths in planar graphs
• New solutions for disjoint paths in P systems
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• Fast distributed DFS solutions for edge-disjoint paths in digraphs

This page was built for publication: An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm

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