Minimum bisection is fixed parameter tractable

DOI10.1145/2591796.2591852zbMath1315.05134arXiv1311.2563MaRDI QIDQ5259566

Marek Cygan, Marcin Pilipczuk, Saket Saurabh, Michał Pilipczuk, Daniel Lokshtanov

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

tree decomposition; fixed-parameter tractability; minimum bisection; randomized contractions

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

05C85: Graph algorithms (graph-theoretic aspects)

05C22: Signed and weighted graphs

Uses Software

• SuLQ