\(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
From MaRDI portal
Publication:1177173
DOI10.1016/0304-3975(91)90072-AzbMath0745.68050MaRDI QIDQ1177173
Publication date: 26 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
Finding optimal subgraphs by local search ⋮ Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy. ⋮ Using maximal independent sets to solve problems in parallel
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Depth-first search is inherently sequential
- Lower bounds on parallel algorithms for finding the first maximal independent set
- Parallelism and the maximal path problem
- The complexity of optimization problems
- A parallelizable lexicographically first maximal edge-induced subgraph problem
- The node-deletion problem for hereditary properties is NP-complete
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- A taxonomy of problems with fast parallel algorithms
- On the complexity of unique solutions
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- Node-Deletion Problems on Bipartite Graphs
- The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
This page was built for publication: \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems