The Computational Complexity of the Tutte Plane: the Bipartite Case
From MaRDI portal
Publication:4291212
DOI10.1017/S0963548300000195zbMath0793.05091WikidataQ60265216 ScholiaQ60265216MaRDI QIDQ4291212
Dirk Vertigan, Dominic J. A. Welsh
Publication date: 5 May 1994
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
computational complexitypartition functionTutte polynomialspanning treesplanar Ising modelTutte plane
Related Items
FPT algorithms to enumerate and count acyclic and totally cyclic orientations, The random cluster process, Complexity of Ising Polynomials, Counting and sampling orientations on chordal graphs, Parameterized counting of trees, forests and matroid bases, Tilings of rectangles with T-tetrominoes, Unnamed Item, Randomised Approximation in the Tutte Plane, Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case, A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs, Unnamed Item, The Tutte polynomial of a class of compound graphs and its applications, Unnamed Item, The Tutte polynomial modulo a prime, The Potts model and the Tutte polynomial, A little statistical mechanics for the graph theorist, Potts model partition functions on two families of fractal lattices, FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES, Graphs with Many Strong Orientations, Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth, A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability, Chromatic polynomials and order ideals of monomials, Forests, colorings and acyclic orientations of the square lattice
Cites Work
