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

DOI10.1016/0020-0190(89)90064-1zbMath0678.68039OpenAlexW2068464125MaRDI QIDQ1124337

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) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (2)

Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations ⋮ Implicit computation of maximum bipartite matchings by sublinear functional operations

Cites Work

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

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