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

DOI10.1016/0020-0190(89)90064-1zbMATH Open0678.68039OpenAlexW2068464125MaRDI QIDQ1124337FDOQ1124337

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

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

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)

Cites Work

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

Cited In (6)

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

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)