On Multiway Cut Parameterized above Lower Bounds

DOI10.1007/978-3-642-28050-4_1zbMath1352.68100arXiv1107.1585MaRDI QIDQ2891333

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk

Publication date: 15 June 2012

Published in: ACM Transactions on Computation Theory, Parameterized and Exact Computation (Search for Journal in Brave)

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

zbMATH Keywords

linear programming; fixed parameter tractability; parameterized algorithms; multiway cut

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C05: Linear programming

90C27: Combinatorial optimization

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity