The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3848625 (Why is no real title available?)
- scientific article; zbMATH DE number 3259770 (Why is no real title available?)
- A parallelizable lexicographically first maximal edge-induced subgraph problem
- A taxonomy of problems with fast parallel algorithms
- An observation on time-storage trade off
- Complete problems for deterministic polynomial time
- Depth-first search is inherently sequential
- Efficient Planarity Testing
- Linear algorithms to recognize outerplanar and maximal outerplanar graphs
- Linear programming is log-space hard for P
- Lower bounds on parallel algorithms for finding the first maximal independent set
- Node-Deletion Problems on Bipartite Graphs
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- On uniform circuit complexity
- Parallelism and the maximal path problem
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The Nielsen reduction and P-complete problems in free groups
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The maximum flow problem is log space complete for P
- The node-deletion problem for hereditary properties is NP-complete
Cited in
(13)- Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy.
- Ordered vertex removal and subgraph problems
- Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
- scientific article; zbMATH DE number 4047154 (Why is no real title available?)
- scientific article; zbMATH DE number 4060745 (Why is no real title available?)
- The parallel complexity of elimination ordering procedures
- Using maximal independent sets to solve problems in parallel
- 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
- \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
- scientific article; zbMATH DE number 2044949 (Why is no real title available?)
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)
