|
|||||
|
|
Optimization via enumeration: a new algorithm for the Max Cut Problem |
|
| Authors: | Anna Galluccio Martin Loebl Jan Vondrák |
| Institution: | (1) Istituto di Analisi dei Sistemi ed Informatica – CNR, viale Manzoni 30, 00185 Roma, Italy, email: galluccio@iasi.rm.cnr.it, IT;(2) Department of Applied Mathematics, Charles University, Malostránske nám. 25, 11800 Praha, Czech Republic, email: {loebl,vondrak}@kam.ms.mff.cuni.cz, CZ |
| 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. Received: June 1999 / Accepted: December 2000?Published online March 22, 2001 |
| Keywords: | : cut – generating function – Pfaffian orientation – modular arithmetics |
| 本文献已被 SpringerLink 等数据库收录！ | |