Hard Enumeration Problems in Geometry and Combinatorics
From MaRDI portal
Publication:3730017
DOI10.1137/0607036zbMath0596.68041WikidataQ56504779 ScholiaQ56504779MaRDI QIDQ3730017
Publication date: 1986
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/76b96735bd6b68640c41abab603e2278e4715fa7
68Q25: Analysis of algorithms and problem complexity
05A15: Exact enumeration problems, generating functions
Related Items
The Computational Complexity of the Tutte Plane: the Bipartite Case, On the computational complexity of the Jones and Tutte polynomials, On unique graph 3-colorability and parsimonious reductions in the plane, A note on a counting problem arising in percolation theory, Towards a dichotomy theorem for the counting constraint satisfaction problem, Inapproximability of the Tutte polynomial, Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions, From a zoo to a zoology: Towards a general theory of graph polynomials, Monomial bases for broken circuit complexes, Enumerative techniques for solving some nonconvex global optimization problems, Counting linear extensions, A weighted graph polynomial from chromatic invariants of knots, The maximum clique problem, On the complexity of some basic problems in computational convexity. I. Containment problems, On enumerating all minimal solutions of feedback problems, Elements of a theory of simulation. II: Sequential dynamical systems., Largest \(j\)-simplices in \(n\)-polytopes, Searching for acyclic orientations of graphs, Signable posets and partitionable simplicial complexes, Minimum concave-cost network flow problems: Applications, complexity, and algorithms, Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph, Subtractive reductions and complete problems for counting complexity classes, Complexity and algorithms for computing Voronoi cells of lattices, A Dichotomy Theorem for Polynomial Evaluation, Complexity of the Bollobás-Riordan Polynomial, Connection Matrices for MSOL-Definable Structural Invariants
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Two combinatorial applications of the Aleksandrov-Fenchel inequalities
- Acyclic orientations of graphs
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- An Algorithm for Distinct Representatives
- The Information-Theoretic Bound is Good for Merging
- The Complexity of Enumeration and Reliability Problems
