Name
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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/PL00011425 | Math. Program. |
Keywords | Field | DocType |
Key words: cut – generating function – Pfaffian orientation – modular arithmetics | Discrete mathematics,Combinatorics,Polynomial,Absolute value,Enumeration,Algorithm,Degree of a polynomial,Matrix polynomial,Time complexity,Maximum cut,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
90 | 2 | 0025-5610 |
Citations | PageRank | References |
11 | 1.39 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anna Galluccio | 1 | 193 | 23.05 |
| Martin Loebl | 2 | 152 | 28.66 |
| j vond v r ak | 3 | 11 | 1.39 |