Name
Title | ||
|---|---|---|
On the Theory of Pfaffian Orientations. II. T-joins, k-cuts, and Duality of Enumeration |
Abstract | ||
|---|---|---|
This is a continuation of our paper \A Theory of Pfaan Orientations I: Perfect Matchings and Permanents". We present a new combinatorial way to compute the generating functions of T -joins and k-cuts of graphs. As a consequence, we show that the computational problem to nd the maximum weight of an edge-cut is polynomially solvable for the instances (G;w) where G is a graph embedded on an arbitrary xed orientable surface and the weight function w has only a bounded number of dierent values. We also survey the related results concerning a duality of the Tutte polynomial, and present an application for the weight enumerator of a binary code. In a continuation of this paper which is in preparation we present an application to the Ising problem of three-dimensional crystal structures. |
Year | Venue | Keywords |
|---|---|---|
1999 | Electr. J. Comb. | tutte polynomial,generating function |
Field | DocType | Volume |
Discrete mathematics,Joins,Combinatorics,Enumeration,Duality (optimization),Pfaffian,Mathematics | Journal | 6 |
Citations | PageRank | References |
1 | 0.42 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anna Galluccio | 1 | 193 | 23.05 |
| Martin Loebl | 2 | 152 | 28.66 |