On the Parameterized Complexity of Contraction to Generalization of Trees.
From MaRDI portal
Publication:5111860
DOI10.4230/LIPIcs.IPEC.2017.1zbMath1435.68120arXiv1708.00622OpenAlexW2909582894MaRDI QIDQ5111860
Prafullkumar Tale, Saket Saurabh, Akanksha Agrawal
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1708.00622
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Reducing the vertex cover number via edge contractions ⋮ Lossy kernelization of same-size clustering
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Parameterized complexity of three edge contraction problems with degree constraints
- Improved kernel results for some FPT problems based on simple observations
- Edge-contraction problems
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On the NP-hardness of edge-deletion and -contraction problems
- Obtaining planarity by contracting few edges
- Contracting graphs to paths and trees
- A faster FPT algorithm for bipartite contraction
- Parametrized complexity theory.
- Contracting Few Edges to Remove Forbidden Induced Subgraphs
- On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
- Deterministic Parameterized Connected Vertex Cover
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
