An improved linear kernel for the cycle contraction problem

DOI10.1016/j.ipl.2019.05.003zbMath1461.05222arXiv1706.05628OpenAlexW2947537480MaRDI QIDQ2274484

Yanyan Li

Publication date: 20 September 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.05628

zbMATH Keywords

graph algorithmsedge contractionlinear kernelparameterized tractability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Contracting to a longest path in H-free graphs

Cites Work

• Unnamed Item
• Increasing the minimum degree of a graph by contractions
• Editing graphs to satisfy degree constraints: a parameterized approach
• Parameterized complexity of three edge contraction problems with degree constraints
• Improved kernel results for some FPT problems based on simple observations
• Obtaining split graphs by edge contraction
• Obtaining planarity by contracting few edges
• Contracting graphs to paths and trees
• A faster FPT algorithm for bipartite contraction
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• Obtaining a Bipartite Graph by Contracting Few Edges

This page was built for publication: An improved linear kernel for the cycle contraction problem