On the Parameterized Complexity Of Grid Contraction

DOI10.4230/LIPICS.SWAT.2020.34MaRDI QIDQ6059202zbMATH OpenOpenAlexFDO

Authors Saket Saurabh, Uéverton dos Santos Souza, Prafullkumar Tale

Publication date 2 November 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2020/12281/pdf/LIPIcs-SWAT-2020-34.pdf/

zbMATH Keywords

FPTgrid contractionkernelizationlower bound

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(10)

• On the parameterized complexity of grid contraction
• A single exponential-time FPT algorithm for cactus contraction
• The hardness of the grid problemGi Under the Routine Resolution Method
• Dimension Bound for Badly Approximable Grids
• On the Parameterized Complexity of Maximum Degree Contraction Problem.
• Reducing the vertex cover number via edge contractions
• Parameterized complexity of biclique contraction and balanced biclique contraction
• Revisiting path contraction and cycle contraction
• The complexity of contracting bipartite graphs into small cycles
• On the parameterized complexity of maximum degree contraction problem

This page was built for publication: On the Parameterized Complexity Of Grid Contraction

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