scientific article; zbMATH DE number 1545676
From MaRDI portal
Publication:4521549
DOI<260::AID-RSA5>3.0.CO;2-W 10.1002/1098-2418(200010/12)17:3/4<260::AID-RSA5>3.0.CO;2-WzbMath0965.68073MaRDI QIDQ4521549
Catherine Greenhill, Martin Dyer
Publication date: 29 July 2001
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Dichotomies for classes of homomorphism problems involving unary functions, Complexity issues on bounded restrictive \(H\)-coloring, Counting and sampling \(H\)-colourings, The complexity of weighted Boolean \#CSP with mixed signs, Approximately Counting H-Colourings is $$\#\mathrm {BIS}$$-Hard, Counting Homomorphisms to Square-Free Graphs, Modulo 2, Some complete and intermediate polynomials in algebraic complexity theory, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Counting \(4 \times 4\) matrix partitions of graphs, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, Holant problems for 3-regular graphs with complex edge functions, Complexity of Ising Polynomials, List homomorphisms of graphs with bounded degrees, Classification of a Class of Counting Problems Using Holographic Reductions, The Complexity of Boolean Holant Problems with Nonnegative Weights, Towards a dichotomy theorem for the counting constraint satisfaction problem, The Complexity of Approximately Counting Tree Homomorphisms, Holographic reduction, interpolation and hardness, Counting List Matrix Partitions of Graphs, Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions, Complexity of correspondence \(H\)-colourings, The complexity of complex weighted Boolean \#CSP, The complexity of generalized domino tilings, A dichotomy for bounded degree graph homomorphisms with nonnegative weights, Parameterised counting in logspace, Complexity classification of the eight-vertex model, The challenges of unbounded treewidth in parameterised subgraph counting problems, Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy., Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants, The complexity of weighted and unweighted \(\#\)CSP, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Unnamed Item, The computational complexity of Holant problems on 3-regular graphs, Unnamed Item, Holographic algorithms beyond matchgates, A note on random homomorphism from arbitrary graphs to \(\mathbb{Z}\), The enumeration of vertex induced subgraphs with respect to the number of components, Distinguishing graphs by their left and right homomorphism profiles, Unnamed Item, Dismantlability, connectedness, and mixing in relational structures, Counting Constraint Satisfaction Problems., Efficient algorithms for counting parameterized list \(H\)-colorings, Inapproximability of the Tutte polynomial, The worm process for the Ising model is rapidly mixing, On the complexity of generalized chromatic polynomials, Lee-Yang theorems and the complexity of computing averages, Spin systems on \(k\)-regular graphs with complex edge functions, A computational proof of complexity of some restricted counting problems, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, The restrictive \(H\)-coloring problem, The complexity of planar Boolean \#CSP with complex weights, An approximation trichotomy for Boolean \#CSP, The complexity of counting homomorphisms seen from the other side, Unnamed Item, On systematic scan for sampling H-colorings of the path, Unnamed Item, Unnamed Item, Zero-free regions of partition functions with applications to algorithms and graph limits, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard, From a zoo to a zoology: Towards a general theory of graph polynomials, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems, Dismantlability, Connectedness, and Mixing in Relational Structures, The complexity of counting homomorphisms to cactus graphs modulo 2, The Complexity of Counting Surjective Homomorphisms and Compactions, Approximate Counting via Correlation Decay in Spin Systems, \(H\)-colouring \(P_t\)-free graphs in subexponential time, A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2, The complexity of partition functions, The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
Cites Work
