Exact and parameterized algorithms for the independent cutset problem

DOI10.1016/J.JCSS.2024.103598MaRDI QIDQ6655670zbMATH OpenFDO

Authors Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza

Publication date 27 December 2024

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2024.103598

zbMATH Keywords

exact algorithmsindependent cutsetparameterized algorithms

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Exact and Parameterized Algorithms for the Independent Cutset Problem
• Fragile graphs with small independent cuts
• \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A new characterization of P_k-free graphs
• A note on fragile graphs
• Approximating clique-width and branch-width
• Chordal deletion is fixed-parameter tractable
• Coloring graphs with stable cutsets
• Complexity results on graphs with few cliques
• Dominating cliques in \(P_ 5\)-free graphs
• Dominating cliques in graphs
• Extremal graphs having no stable cutset
• Faster parameterized algorithms using linear programming
• Finding odd cycle transversals.
• Finding small separators in linear time via treewidth reduction
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 910864 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• On cliques in graphs
• On diameters and radii of bridged graphs
• On generating all maximal independent sets
• On stable cutsets in claw-free graphs and planar graphs
• On stable cutsets in graphs
• On stable cutsets in line graphs
• Parameterized algorithms
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• Recognizing decomposable graphs
• Stable set bonding in perfect graphs and parity graphs

Cited in

(3)

• Exact and Parameterized Algorithms for the Independent Cutset Problem
• On polynomial kernelization for stable cutset
• A faster algorithm for independent cut

This page was built for publication: Exact and parameterized algorithms for the independent cutset problem

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