The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem

DOI10.1007/BF01374523zbMath0751.68028MaRDI QIDQ4009810

Raymond Greenlaw

Publication date: 27 September 1992

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

parallel complexity; approximation algorithms; EREW PRAM; maximum acyclic subgraph problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

Finding optimal subgraphs by local search

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