Twin-width and polynomial kernels

DOI10.4230/LIPICS.IPEC.2021.10MaRDI QIDQ6192478zbMATH OpenFDO

Authors Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant

Publication date 12 February 2024

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2021.10

zbMATH Keywords

dominating setkernelizationlower boundstwin-width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Recommendations

• Twin-width and polynomial kernels
• Twin-width. III: Max independent set, min dominating set, and coloring
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Tight kernel bounds for problems on graphs with small degeneracy
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy

Cited in

(5)

• Planar graph with twin-width seven
• Twin-width. III: Max independent set, min dominating set, and coloring
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
• Faster graph algorithms through DAG compression
• Twin-width of graphs on surfaces

This page was built for publication: Twin-width and polynomial kernels

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