A single exponential-time FPT algorithm for cactus contraction

DOI10.1016/j.tcs.2023.113803OpenAlexW4323543519MaRDI QIDQ2697543

Pranabendu Misra, Prafullkumar Tale, R. Krithika

Publication date: 12 April 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113803

zbMATH Keywords

cactus graphsgraph contractionfixed parameter tractable algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Increasing the minimum degree of a graph by contractions
• Parameterized complexity of three edge contraction problems with degree constraints
• Edge-contraction problems
• On the parameterized complexity of maximum degree contraction problem
• On the removal of forbidden graphs by edge-deletion or by edge- contraction
• On the NP-hardness of edge-deletion and -contraction problems
• Obtaining planarity by contracting few edges
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• On the parameterized complexity of contraction to generalization of trees
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Contracting graphs to paths and trees
• 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
• Lossy Kernels for Graph Contraction Problems
• Kernelization
• Split Contraction
• Paths to Trees and Cacti
• Obtaining a Bipartite Graph by Contracting Few Edges
• Parameterized Algorithms
• On the Parameterized Complexity Of Grid Contraction

This page was built for publication: A single exponential-time FPT algorithm for cactus contraction