On the parameterized complexity of contraction to generalization of trees
DOI10.1007/S00224-018-9892-ZzbMATH Open1435.68119OpenAlexW2962676809WikidataQ128972590 ScholiaQ128972590MaRDI QIDQ2000005FDOQ2000005
Saket Saurabh, Akanksha Agarwal, Prafullkumar Tale
Publication date: 27 June 2019
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8544/
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Fundamentals of parameterized complexity
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On problems without polynomial kernels
- Parametrized complexity theory.
- Title not available (Why is that?)
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Contracting graphs to paths and trees
- Obtaining planarity by contracting few edges
- Obtaining a Bipartite Graph by Contracting Few Edges
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- On the NP-hardness of edge-deletion and -contraction problems
- Edge-contraction problems
- A faster FPT algorithm for bipartite contraction
- Contracting Few Edges to Remove Forbidden Induced Subgraphs
- On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
- Parameterized complexity of three edge contraction problems with degree constraints
- Deterministic Parameterized Connected Vertex Cover
- Improved kernel results for some FPT problems based on simple observations
- Lossy kernelization
- Paths to Trees and Cacti
- Title not available (Why is that?)
Cited In (8)
- \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
- Reducing the vertex cover number via edge contractions
- On the parameterized complexity of maximum degree contraction problem
- Contracting to a longest path in H-free graphs
- On the Parameterized Complexity of Maximum Degree Contraction Problem.
- On the parameterized complexity of grid contraction
- A single exponential-time FPT algorithm for cactus contraction
- Lossy kernelization of same-size clustering
This page was built for publication: On the parameterized complexity of contraction to generalization of trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2000005)
