Parallelism and the maximal path problem

DOI10.1016/0020-0190(87)90105-0zbMATH Open0637.68079OpenAlexW2081298180MaRDI QIDQ1098641FDOQ1098641

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

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

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)

Cites Work

• A taxonomy of problems with fast parallel algorithms
• An optimal parallel connectivity algorithm
• Parallelism in random access machines
• Title not available (Why is that?)

Cited In (20)

• On the complexity of optimal parallel cooperative path-finding
• Title not available (Why is that?)
• \(\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
• Developments in Language Theory
• An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• On legal path problems in digraphs
• 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)