The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
From MaRDI portal
Publication:4009810
DOI10.1007/BF01374523zbMath0751.68028MaRDI QIDQ4009810
Publication date: 27 September 1992
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ordered vertex removal and subgraph problems
- Parallelism and the feedback vertex set problem
- The maximum flow problem is log space complete for P
- A model classifying algorithms as inherently sequential with applications to graph searching
- A taxonomy of problems with fast parallel algorithms
- Feedback vertex sets and cyclically reducible graphs
- The complexity of minimum cut and maximum flow problems in an acyclic network
- Finding a minimum feedback arc set in reducible flow graphs
- A contraction algorithm for finding small cycle cutsets
- A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
- The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
- Flow Graph Reducibility
This page was built for publication: The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem