The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

DOI10.1007/BF02088292zbMath0679.68090OpenAlexW1498460077MaRDI QIDQ4729355

Satoru Miyano

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1007/bf02088292

zbMATH Keywords

P-completenessNC algorithmslfm subgraph problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem ⋮ Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy. ⋮ The parallel complexity of elimination ordering procedures ⋮ \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems ⋮ Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity ⋮ Using maximal independent sets to solve problems in parallel ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ A MEASURE FOR THE LEXICOGRAPHICALLY FIRST MAXIMAL INDEPENDENT SET PROBLEM AND ITS LIMITS

Cites Work

• Unnamed Item
• Unnamed Item
• The Nielsen reduction and P-complete problems in free groups
• Depth-first search is inherently sequential
• Lower bounds on parallel algorithms for finding the first maximal independent set
• Parallelism and the maximal path problem
• A parallelizable lexicographically first maximal edge-induced subgraph problem
• The node-deletion problem for hereditary properties is NP-complete
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• On the removal of forbidden graphs by edge-deletion or by edge- contraction
• On uniform circuit complexity
• The maximum flow problem is log space complete for P
• An observation on time-storage trade off
• Complete problems for deterministic polynomial time
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Linear programming is log-space hard for P
• A taxonomy of problems with fast parallel algorithms
• Node-Deletion Problems on Bipartite Graphs
• Efficient Planarity Testing
• The Rectilinear Steiner Tree Problem is $NP$-Complete