Breaking a graph into connected components with small dominating sets

DOI10.4230/LIPICS.MFCS.2024.24MaRDI QIDQ7241024zbMATH OpenFDO

Authors Matthias Bentert, Michael R. Fellows, Petr A. Golovach, Frances Rosamond, Saket Saurabh

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2024.24

zbMATH Keywords

degeneracyparameterized algorithmspolynomial kernelsrecursive understanding

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A faster algorithm for vertex cover parameterized by solution size
• A more relaxed model for graph-based data clustering: s-plex cluster editing
• Approximation and tidying -- a problem kernel for s-plex cluster vertex deletion
• Designing FPT algorithms for cut problems using randomized contractions
• FPT algorithms for domination in sparse graphs and beyond
• Faster parameterized algorithm for cluster vertex deletion
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fundamentals of parameterized complexity
• Kernelization Lower Bounds by Cross-Composition
• Kernelization for graph packing problems via rainbow matching
• Minimum bisection is fixed-parameter tractable
• On 2-clubs in graph-based data clustering: theory and algorithm engineering
• On Editing Graphs into 2-Club Clusters
• Parameterized algorithms
• Reducing CMSO model checking to highly connected graphs
• Some simplified NP-complete graph problems
• The node-deletion problem for hereditary properties is NP-complete
• Using expander graphs to find vertex connectivity
• Which problems have strongly exponential complexity?

This page was built for publication: Breaking a graph into connected components with small dominating sets

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