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 (22)

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

This page was built for publication: Edge-contraction problems