| Article ID: | iaor2002900 |
| Country: | Germany |
| Volume: | 90 |
| Issue: | 2 |
| Start Page Number: | 273 |
| End Page Number: | 290 |
| Publication Date: | Jan 2001 |
| Journal: | Mathematical Programming |
| Authors: | Galluccio A., Loebl M., Vondrk J. |
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.