Contracting few edges to remove forbidden induced subgraphs

DOI10.1007/978-3-319-03898-8_10MaRDI QIDQ2867076zbMATH OpenOpenAlexFDO

Authors Leizhen Cai, Chengwei Guo

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)

Recommendations

• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• Contraction Blockers for Graphs with Forbidden Induced Paths
• On the parameterized approximability of contraction to classes of chordal graphs

Cited in

(19)

• Forbidden induced subgraph characterization of cograph contractions
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• Parameterized complexity of three edge contraction problems with degree constraints
• Contraction Blockers for Graphs with Forbidden Induced Paths
• On the Parameterized Complexity of Maximum Degree Contraction Problem.
• Reducing graph transversals via edge contractions
• On the parameterized complexity of contraction to generalization of trees
• On the parameterized approximability of contraction to classes of chordal graphs
• Reducing the vertex cover number via edge contractions
• Obtaining split graphs by edge contraction
• On the parameterized complexity of maximum degree contraction problem
• A single exponential-time FPT algorithm for cactus contraction
• Contracting to a longest path in H-free graphs
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• On the parameterized complexity of grid contraction
• On the parameterized complexity of contraction to generalization of trees
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Paths to trees and cacti
• Paths to trees and cacti

This page was built for publication: Contracting few edges to remove forbidden induced subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867076)