Faster parameterized algorithms for deletion to split graphs

DOI10.1007/978-3-642-31155-0_10MaRDI QIDQ2904547zbMATH OpenOpenAlexFDO

Authors Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan

Publication date 14 August 2012

Published in Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31155-0_10

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Faster parameterized algorithms for deletion to split graphs
• Quadratic vertex kernel for split vertex deletion
• Quadratic vertex kernel for split vertex deletion
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• Algorithms for deletion problems on split graphs

Cited in

(16)

• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• Faster FPT algorithms for deletion to pairs of graph classes
• Faster parameterized algorithms for deletion to split graphs
• Polynomial kernelization for removing induced claws and diamonds
• Faster parameterized algorithm for pumpkin vertex deletion set
• Algorithms for deletion problems on split graphs
• Polynomial kernelization for removing induced claws and diamonds
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Parameterized algorithms for deletion to (r,)-graphs
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Quadratic vertex kernel for split vertex deletion
• Vertex deletion on split graphs: beyond 4-hitting set
• A simple \((2 + \epsilon)\)-approximation algorithm for split vertex deletion
• Obtaining split graphs by edge contraction

This page was built for publication: Faster parameterized algorithms for deletion to split graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904547)