Edge-contraction problems

DOI10.1016/0022-0000(83)90012-0zbMath0539.68034OpenAlexW2062347470MaRDI QIDQ794164

Tomio Hirata, Takao Asano

Publication date: 1983

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(83)90012-0

zbMATH Keywords

NP-completenessedge-contraction problem

Mathematics Subject Classification ID

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

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, The complexity of degree anonymization by graph contractions, Increasing the minimum degree of a graph by contractions, On the parameterized complexity of grid contraction, How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks, A single exponential-time FPT algorithm for cactus contraction, Contracting graphs to paths and trees, Parameterized complexity of three edge contraction problems with degree constraints, Path Contraction Faster than $2^n$, Improved kernel results for some FPT problems based on simple observations, On the Parameterized Complexity of Maximum Degree Contraction Problem., Paths to trees and cacti, On the parameterized complexity of contraction to generalization of trees, The computational complexity of disconnected cut and \(2 K_2\)-partition, Graph theory (algorithmic, algebraic, and metric problems), Contracting chordal graphs and bipartite graphs to paths and trees, Contracting chordal graphs and bipartite graphs to paths and trees, Path Contraction Faster Than 2^n, On the Parameterized Complexity of Contraction to Generalization of Trees., On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The node-deletion problem for hereditary properties is NP-complete
• 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
• Edge-Deletion Problems
• Node-Deletion Problems on Bipartite Graphs
• Efficient Planarity Testing
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• On the Computational Complexity of Combinatorial Problems
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Matching, Euler tours and the Chinese postman
• Dividing a Graph into Triconnected Components
• Node-and edge-deletion NP-complete problems
• On the complexity of the Maximum Subgraph Problem