Exact and parameterized algorithms for the independent cutset problem

DOI10.1016/j.jcss.2024.103598MaRDI QIDQ6655670

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

Publication date: 27 December 2024

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

zbMATH Keywords

parameterized algorithmsexact algorithmsindependent cutset

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new characterization of \(P_k\)-free graphs
• Finding odd cycle transversals.
• On stable cutsets in claw-free graphs and planar graphs
• Chordal deletion is fixed-parameter tractable
• On generating all maximal independent sets
• On diameters and radii of bridged graphs
• Coloring graphs with stable cutsets
• Dominating cliques in \(P_ 5\)-free graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Stable set bonding in perfect graphs and parity graphs
• On stable cutsets in line graphs
• On stable cutsets in graphs
• A note on fragile graphs
• Extremal graphs having no stable cutset
• Linear time solvable optimization problems on graphs of bounded clique-width
• Approximating clique-width and branch-width
• Finding small separators in linear time via treewidth reduction
• Recognizing decomposable graphs
• Faster Parameterized Algorithms Using Linear Programming
• Parameterized Algorithms
• On cliques in graphs
• Dominating cliques in graphs
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs

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