Abstract.
We present a polynomial time algorithm to find the maximum weight of an edge-cut in graphs embeddable on an arbitrary orientable surface, with integral weights bounded in the absolute value by a polynomial of the size of the graph.</
The algorithm has been implemented for toroidal grids using modular arithmetics and the generalized nested dissection method. The applications in statistical physics are discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: June 1999 / Accepted: December 2000¶Published online March 22, 2001
Rights and permissions
About this article
Cite this article
Galluccio, A., Loebl, M. & Vondrák, J. Optimization via enumeration: a new algorithm for the Max Cut Problem. Math. Program. 90, 273–290 (2001). https://doi.org/10.1007/PL00011425
Issue Date:
DOI: https://doi.org/10.1007/PL00011425