A faster algorithm for independent cut

DOI10.1016/J.TCS.2025.115542MaRDI QIDQ6914009zbMATH OpenFDO

Authors Vsevolod L. Chernyshev, Johannes Rauch, Dieter Rautenbach, Liliia Redina

Publication date 17 October 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115542

zbMATH Keywords

independent cut

Mathematics Subject Classification ID

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)

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A note on fragile graphs
• Exact and parameterized algorithms for the independent cutset problem
• Extremal graphs having no stable cutset
• Graph Classes: A Survey
• On cliques in graphs
• On generating all maximal independent sets
• On polynomial kernelization for stable cutset
• On stable cutsets in claw-free graphs and planar graphs
• On stable cutsets in graphs
• On stable cutsets in line graphs
• On the complexity of k-SAT
• Parameterized algorithms
• The complexity of satisfiability problems
• Which problems have strongly exponential complexity?

This page was built for publication: A faster algorithm for independent cut

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