On the NP-hardness of edge-deletion and -contraction problems
From MaRDI portal
Publication:1838829
DOI10.1016/0166-218X(83)90101-4zbMath0511.68028OpenAlexW2022137727MaRDI QIDQ1838829
Publication date: 1983
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(83)90101-4
Related Items
Paths to Trees and Cacti, Increasing the Minimum Degree of a Graph by Contractions, On the parameterized complexity of maximum degree contraction problem, Deleting edges to restrict the size of an epidemic: a new application for treewidth, Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth, Parameterized complexity of fair deletion problems, Increasing the minimum degree of a graph by contractions, Contraction Blockers for Graphs with Forbidden Induced Paths, On the parameterized complexity of grid contraction, Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem, Reducing the vertex cover number via edge contractions, Classical and quantum compression for edge computing: the ubiquitous data dimensionality reduction, The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases, A single exponential-time FPT algorithm for cactus contraction, Contracting graphs to paths and trees, Path Contraction Faster than $2^n$, On the Parameterized Complexity of Maximum Degree Contraction Problem., Paths to trees and cacti, On the parameterized complexity of contraction to generalization of trees, Unnamed Item, Graph theory (algorithmic, algebraic, and metric problems), Reducing graph transversals via edge contractions, Path Contraction Faster Than 2^n, Complexity and algorithms for constant diameter augmentation problems, On the Parameterized Complexity of Contraction to Generalization of Trees., On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
Cites Work
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Parallel concepts in graph theory
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- Node-Deletion NP-Complete Problems
- On the Computational Complexity of Combinatorial Problems
- `` Strong NP-Completeness Results
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Dividing a Graph into Triconnected Components
- Node-and edge-deletion NP-complete problems
- The complexity of theorem-proving procedures
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
