The minimum \(k\)-way cut of bounded size is fixed-parameter tractable. (English) Zbl 1292.68094
Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 160-169 (2011).
MSC:
68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
05C85 | Graph algorithms (graph-theoretic aspects) |
68R10 | Graph theory (including graph drawing) in computer science |
05C10 | Planar graphs; geometric and topological aspects of graph theory |
05C40 | Connectivity |