Randomized Contractions Meet Lean Decompositions

DOI10.1145/3426738OpenAlexW3113894442MaRDI QIDQ5028343FDOQ5028343

Marcin Pilipczuk, Daniel Lokshtanov, Saket Saurabh, Marek Cygan, Michał Pilipczuk, Paweł Komosa, 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)

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)