Parallelism and the maximal path problem

DOI10.1016/0020-0190(87)90105-0MaRDI QIDQ1098641zbMATH OpenOpenAlexFDO

Authors 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 complexityparallel algorithmplanar graphsP-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)

Recommendations

• A parallel algorithm for the maximal path problem
• Parallel complexity of computing a maximal set of disjoint paths
• Fast RNC and NC algorithms for maximal path sets
• Parallel algorithms for maximal acyclic sets
• Using maximal independent sets to solve problems in parallel

Cites work

• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• An optimal parallel connectivity algorithm
• Parallelism in random access machines

Cited in

(20)

• On the complexity of optimal parallel cooperative path-finding
• scientific article; zbMATH DE number 714465 (Why is no real title available?)
• \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
• Fast Parallel Algorithms for All-Sources Lexicographic Search and Path-Algebra Problems
• The computational complexity of pattern formation
• Frameworks for designing in-place graph algorithms
• The lexicographically first topological order problem is NLOG-complete
• A framework for in-place graph algorithms
• Depth-First Search Using $$O(n)$$ Bits
• Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph
• The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
• Parallel complexity of computing a maximal set of disjoint paths
• A measure for the lexicographically first maximal independent set problem and its limits
• An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm
• Developments in Language Theory
• On legal path problems in digraphs
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• A parallel algorithm for the maximal path problem
• On parallelizing a greedy heuristic for finding small dominant sets
• Using maximal independent sets to solve problems in parallel

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

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