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

lean decompositionsminimum bisectionrandomized 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

(14)

• 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
• 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
• Flow-augmentation. I: Directed graphs
• Two-sets cut-uncut on planar graphs
• Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
• Flow-augmentation. II: Undirected graphs
• Matching (multi)cut: algorithms, complexity, and enumeration
• Advances in algorithmic meta theorems (invited paper)
• Elimination distance to dominated clusters
• All-subsets important separators with applications to sample sets, balanced separators and vertex sparsifiers in directed graphs

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)