Randomized Contractions Meet Lean Decompositions

DOI10.1145/3426738OpenAlexW3113894442MaRDI QIDQ5028343FDOQ5028343

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

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

zbMATH Keywords

minimum bisectionlean decompositionsrandomized contractions

Mathematics Subject Classification ID

Computer science (68-XX)

Cited In (6)

• Partitioning subclasses of chordal graphs with few deletions
• Partitioning subclasses of chordal graphs with few deletions
• On Weighted Graph Separation Problems and Flow Augmentation
• 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

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)