Balanced Judicious Bipartition is Fixed-Parameter Tractable

DOI10.1137/17M1155612zbMath1425.05129arXiv1710.05491MaRDI QIDQ5238741

Meirav Zehavi, Saket Saurabh, Daniel Lokshtanov, Roohani Sharma

Publication date: 28 October 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

tree decomposition; judicious partition; fixed-parameter tractable; minimum bisection; randomized contractions

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

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