Flow-augmentation. II: Undirected graphs

DOI10.1145/3641105MaRDI QIDQ7023567zbMATH OpenFDO

Authors Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström

Publication date 21 February 2025

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3641105

zbMATH Keywords

fixed-parameter tractabilitygraph separation problemsflow-augmentation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Flows in graphs (05C21) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• Designing FPT algorithms for cut problems using randomized contractions
• Directed flow-augmentation
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Flow-augmentation. III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
• List H-coloring a graph by removing few vertices
• Minimum bisection is fixed-parameter tractable
• Multi-budgeted directed cuts
• Multicut Is FPT
• Randomized Contractions Meet Lean Decompositions
• Solving hard cut problems via flow-augmentation

Cited in

(2)

• Flow-augmentation. I: Directed graphs
• Flow-augmentation. III: Complexity dichotomy for Boolean CSPS parameterized by the number of unsatisfied constraints

This page was built for publication: Flow-augmentation. II: Undirected graphs

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