Parallelism and the maximal path problem

DOI10.1016/0020-0190(87)90105-0zbMath0637.68079OpenAlexW2081298180MaRDI QIDQ1098641

Ernst W. Mayr, Richard J. Anderson

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90105-0

zbMATH Keywords

computational complexityplanar graphsparallel algorithmP-completenessmaximal path problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (11)

On parallelizing a greedy heuristic for finding small dominant sets ⋮ A parallel algorithm for the maximal path problem ⋮ Depth-First Search Using $$O(n)$$ Bits ⋮ \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems ⋮ Using maximal independent sets to solve problems in parallel ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ The lexicographically first topological order problem is NLOG-complete ⋮ Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph ⋮ The computational complexity of pattern formation ⋮ The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

Cites Work

• An optimal parallel connectivity algorithm
• A taxonomy of problems with fast parallel algorithms
• Parallelism in random access machines
• Unnamed Item

This page was built for publication: Parallelism and the maximal path problem