\(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems

DOI10.1016/0304-3975(91)90072-AzbMath0745.68050MaRDI QIDQ1177173

Satoru Miyano

Publication date: 26 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

time complexity\(\Delta^ P_ 2\)-completenesslexicographically first maximal subgraph problems

Mathematics Subject Classification ID

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