An improved linear kernel for the cycle contraction problem
From MaRDI portal
Publication:2274484
DOI10.1016/j.ipl.2019.05.003zbMath1461.05222arXiv1706.05628OpenAlexW2947537480MaRDI QIDQ2274484
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
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