Contracting Few Edges to Remove Forbidden Induced Subgraphs

DOI10.1007/978-3-319-03898-8_10zbMath1406.68037OpenAlexW78635179MaRDI QIDQ2867076

Chengwei Guo, Leizhen Cai

Publication date: 10 December 2013

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-03898-8_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

Paths to Trees and Cacti ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Hadwiger Number of Graphs with Small Chordality ⋮ On the parameterized complexity of grid contraction ⋮ Reducing the vertex cover number via edge contractions ⋮ Obtaining split graphs by edge contraction ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Contracting to a longest path in H-free graphs ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Paths to trees and cacti ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ On the Parameterized Complexity of Contraction to Generalization of Trees. ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

This page was built for publication: Contracting Few Edges to Remove Forbidden Induced Subgraphs