scientific article
From MaRDI portal
Publication:3140234
zbMath0799.68008MaRDI QIDQ3140234
Publication date: 26 October 1993
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexitystatistical physicsknot theorycounting problemsknot polynomialsnumber-\(P\)-completeness
Combinatorics in computer science (68R05) Percolation (82B43) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On the Seifert graphs of a link diagram and its parallels, An expectation maximization algorithm for high-dimensional model selection for the Ising model with misclassified states*, On the number of go positions on lattice graphs, Structure of the partition function and transfer matrices for the Potts model in a magnetic field on lattice strips, Evaluations of Graph Polynomials, A Graph Polynomial for Independent Sets of Bipartite Graphs, A Tutte Polynomial for Maps, Edge cut splitting formulas for Tutte-Grothendieck invariants, Unnamed Item, Entropy and enumeration of spanning connected unicyclic subgraphs in self-similar network, Homomorphisms and Polynomial Invariants of Graphs, The geometry of geometries: matroid theory, old and new, Deletion-contraction and the surface Tutte polynomial, Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders, Unnamed Item, On the Potts model partition function in an external field, Enumeration of spanning trees of graphs with rotational symmetry, How many needles are in a haystack, or how to solve \#P-complete counting problems fast, Some Problems on Approximate Counting in Graphs and Matroids, Triangulations of Cayley and Tutte polytopes, Matiyasevich formula for chromatic and flow polynomials and Feynman amplitudes, The number of Reidemeister moves needed for unknotting, Dual complementary polynomials of graphs and combinatorial-geometric interpretation on the values of Tutte polynomial at positive integers, Unnamed Item, Classical Ising model test for quantum circuits, Asymptotic behavior of spanning forests and connected spanning subgraphs on two-dimensional lattices, The Equivalence of Two Graph Polynomials and a Symmetric Function, Modifications of Tutte–Grothendieck invariants and Tutte polynomials, Unnamed Item, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, Generalized loop‐erased random walks and approximate reachability, The Jones polynomial and graphs on surfaces, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, Parity, Eulerian subgraphs and the Tutte polynomial, Structural properties of Potts model partition functions and chromatic polynomials for lattice strips, Exact Potts model partition functions on strips of the honeycomb lattice, Exact Potts model partition functions on wider arbitrary-length strips of the square lattice, Some new evaluations of the Tutte polynomial, On the colored Tutte polynomial of a graph of bounded treewidth, Zeros of Jones polynomials for families of knots and links, The HOMFLY-PT polynomial is fixed-parameter tractable, Hopf algebras and the Penrose polynomial, Connection Matrices for MSOL-Definable Structural Invariants, On metaplectic modular categories and their applications, Excluded Minors and the Ribbon Graphs of Knots, The HOMFLY polynomials of odd polyhedral links, Totally frustrated states in the chromatic theory of gain graphs, New Graph Polynomials from the Bethe Approximation of the Ising Partition Function, Branch decompositions and minor containment, Mathematics of topological quantum computing, The computational complexity of knot genus and spanning area, Unnamed Item, A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability, Study of exponential growth constants of directed heteropolygonal Archimedean lattices, Matroids, delta-matroids and embedded graphs, The complexity of approximating the complex-valued Potts model, Reflection positivity, rank connectivity, and homomorphism of graphs, A note on some inequalities for the Tutte polynomial of a matroid, On matroids determined by their Tutte polynomials, The chip-firing game, Transition polynomials, Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2, A solution to the tennis ball problem, Counting Unlabelled Subtrees of a Tree is #P-complete, The complexity of the Weight Problem for permutation groups, The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs, Markov chain decomposition for convergence rate analysis, Tractability in constraint satisfaction problems: a survey, The complexity of approximating the complex-valued Potts model, The parametrized complexity of knot polynomials, Computing the Tutte polynomial of Archimedean tilings, Counting consistent phylogenetic trees is \#P-complete, Graphs determined by polynomial invariants, The complexity of weighted Boolean \#CSP with mixed signs, The computational complexity of calculating partition functions of optimal medians with Hamming distance, Tutte polynomial of scale-free networks, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, On the number of 3-edge colorings of cubic graphs, The geometry of graphs and some of its algorithmic applications, A general method for computing Tutte polynomials of self-similar graphs, Splitting formulas for Tutte polynomials, Low depth quantum circuits for Ising models, A categorification for the Tutte polynomial, On the evaluation of the Tutte polynomial at the points \((1, -1)\) and \((2, -1)\), Tilings of rectangles with T-tetrominoes, Algorithmic uses of the Feferman-Vaught theorem, Transforms and minors for binary functions, Chromatic polynomial, \(q\)-binomial counting and colored Jones function, New method for counting the number of spanning trees in a two-tree network, Tutte polynomials of bracelets, Inapproximability of the Tutte polynomial of a planar graph, Chip firing and the Tutte polynomial, The complexity of approximating bounded-degree Boolean \(\#\)CSP, Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs, Farrell polynomials on graphs of bounded tree width, On some Tutte polynomial sequences in the square lattice, The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., Some inequalities for the Tutte polynomial, On the coupling time of the heat-bath process for the Fortuin-Kasteleyn random-cluster model, Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems, The Tutte polynomial of some matroids, Lattice path matroids: Enumerative aspects and Tutte polynomials, Tension-flow polynomials on graphs, Distinguishing graphs by their left and right homomorphism profiles, Arrangements, channel assignments, and associated polynomials, The Go polynomials of a graph., Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, On the exact evaluation of certain instances of the Potts partition function by quantum computers, Tutte polynomials of generalized parallel connections, Tutte polynomials and related asymptotic limiting functions for recursive families of graphs, Some results on generalised Whitney functions, The Tutte polynomial modulo a prime, On the algebraic complexity of some families of coloured Tutte polynomials, Recursively constructible families of graphs, Inapproximability of the Tutte polynomial, The complexity of counting edge colorings for simple graphs, Computing the Tutte polynomial of lattice path matroids using determinantal circuits, A simple algorithm to compute link polynomials defined by using skein relations, Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION, Orientations, lattice polytopes, and group arrangements. III: Cartesian product arrangements and applications to Tutte type polynomials, The complexity of the weight problem for permutation and matrix groups., Weighted graph colorings, The contributions of W.T. Tutte to matroid theory, \(G\)-parking functions, acyclic orientations and spanning trees, The bivariate Ising polynomial of a graph, Weighted-set graph colorings, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, A little statistical mechanics for the graph theorist, High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression, The interlace polynomial of a graph, Parallel connections and coloured Tutte polynomials, Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings, A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model, A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan, Interpretations of the Tutte and characteristic polynomials of matroids, Homotopy type of circle graph complexes motivated by extreme Khovanov homology, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, A new connection between quantum circuits, graphs and the Ising partition function, Computing HOMFLY polynomials of 2-bridge links from 4-plat representation, The generating function of planar Eulerian orientations, Efficient Monte Carlo simulation via the generalized splitting method, From a zoo to a zoology: Towards a general theory of graph polynomials, Locally grid graphs: Classification and Tutte uniqueness, A parallel algorithm for ridge-penalized estimation of the multivariate exponential family from data of mixed types, Fast algorithms for computing Jones polynomials of certain links, Enumerating spanning trees of graphs with an involution, The Tutte polynomial as a growth function, Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs, Bicycle dimension and special points of the Tutte polynomial, Polynomials counting nowhere-zero chains in graphs, FKT is not universal -- a planar holant dichotomy for symmetric constraints, Homomorphisms and polynomial invariants of graphs, Exact Potts model partition function on strips of the triangular lattice, A weighted graph polynomial from chromatic invariants of knots, An algorithm for the Tutte polynomials of graphs of bounded treewidth, General structural results for Potts model partition functions on lattice strips, Contraction-deletion invariants for graphs, Irreducibility of the Tutte polynomial of a connected matroid, Polynomials associated with nowhere-zero flows, On the parity of colourings and flows, Forests, colorings and acyclic orientations of the square lattice, Tally NP sets and easy census functions., The computational complexity of knot and matroid polynomials, Irreducibility of the Tutte polynomial of an embedded graph, Matroid invariants and counting graph homomorphisms, On the HOMFLY polynomials of even trigonal bipyramid links
