06086340

a

06086340 Delling, Daniel Werneck, Renato F. Better bounds for graph bisection. Epstein, Leah (ed.) et al., Algorithms -- ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10--12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 407-418 (2012). 2012 Berlin: Springer EN

doi:10.1007/978-3-642-33090-2_36

Summary: We introduce new lower bounds for the minimum graph bisection problem. Within a branch-and-bound framework, they enable the solution of a wide variety of instances with tens of thousands of vertices to optimality. Our algorithm compares favorably with the best previous approaches, solving long-standing open instances in minutes.