Randomized Contractions Meet Lean Decompositions

DOI10.1145/3426738MaRDI QIDQ5028343zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Paweł Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Magnus Wahlström

Publication date 8 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.06864

zbMATH Keywords

minimum bisectionlean decompositionsrandomized contractions

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Minimum bisection is fixed parameter tractable
• Minimum bisection is fixed-parameter tractable
• A Menger-like property of tree-cut width
• Lean Tree-Cut Decompositions: Obstructions and Algorithms
• Algorithms finding tree-decompositions of graphs

Cited in

(6)

• A parameterized approximation scheme for min \(k\)-cut
• Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
• An FPT algorithm for matching cut and d-cut
• Partitioning subclasses of chordal graphs with few deletions
• Partitioning subclasses of chordal graphs with few deletions
• On Weighted Graph Separation Problems and Flow Augmentation

This page was built for publication: Randomized Contractions Meet Lean Decompositions

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