The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
From MaRDI portal
DOI10.1007/BF02088292zbMATH Open0679.68090OpenAlexW1498460077MaRDI QIDQ4729355FDOQ4729355
Authors: 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Cites Work
- The node-deletion problem for hereditary properties is NP-complete
- On uniform circuit complexity
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- A taxonomy of problems with fast parallel algorithms
- Efficient Planarity Testing
- An observation on time-storage trade off
- Node-Deletion Problems on Bipartite Graphs
- Title not available (Why is that?)
- Depth-first search is inherently sequential
- Complete problems for deterministic polynomial time
- Linear algorithms to recognize outerplanar and maximal outerplanar graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Linear programming is log-space hard for P
- Title not available (Why is that?)
- Parallelism and the maximal path problem
- A parallelizable lexicographically first maximal edge-induced subgraph problem
- Lower bounds on parallel algorithms for finding the first maximal independent set
- The Nielsen reduction and P-complete problems in free groups
- The maximum flow problem is log space complete for P
Cited In (13)
- \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
- Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy.
- The parallel complexity of elimination ordering procedures
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Ordered vertex removal and subgraph problems
- Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
- Monadic second-order evaluations on tree-decomposable graphs
- The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
- A measure for the lexicographically first maximal independent set problem and its limits
- On the parameterized parallel complexity and the vertex cover problem
- Using maximal independent sets to solve problems in parallel
This page was built for publication: The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729355)
