Hard Enumeration Problems in Geometry and Combinatorics
From MaRDI portal
Publication:3730017
DOI10.1137/0607036zbMath0596.68041OpenAlexW2000930415WikidataQ56504779 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
Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15)
Related Items (46)
On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Largest \(j\)-simplices in \(n\)-polytopes ⋮ Harary polynomials ⋮ On enumerating all minimal solutions of feedback problems ⋮ Block interpolation: a framework for tight exponential-time counting complexity ⋮ Searching for acyclic orientations of graphs ⋮ A Dichotomy Theorem for Polynomial Evaluation ⋮ Enumerative techniques for solving some nonconvex global optimization problems ⋮ Efficient enumeration of graph orientations with sources ⋮ Counting and sampling orientations on chordal graphs ⋮ The Computational Complexity of the Tutte Plane: the Bipartite Case ⋮ Signable posets and partitionable simplicial complexes ⋮ On unique graph 3-colorability and parsimonious reductions in the plane ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Complexity of the Bollobás-Riordan Polynomial ⋮ Combinatorial Generation via Permutation Languages. V. Acyclic Orientations ⋮ Eigenpolytope Universality and Graphical Designs ⋮ Complexity and approximability of the cover polynomial ⋮ Short certificates for chromatic equivalence ⋮ Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms ⋮ Laplacian ideals, arrangements, and resolutions ⋮ Counting polygon triangulations is hard ⋮ Inapproximability of the Tutte polynomial ⋮ Counting linear extensions ⋮ The harmonic polytope ⋮ On the complexity of generalized chromatic polynomials ⋮ Acyclic polynomials of graphs ⋮ A note on a counting problem arising in percolation theory ⋮ On the number of upward planar orientations of maximal planar graphs ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ Unnamed Item ⋮ Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions ⋮ Complexity and algorithms for computing Voronoi cells of lattices ⋮ Connection Matrices for MSOL-Definable Structural Invariants ⋮ Minimum concave-cost network flow problems: Applications, complexity, and algorithms ⋮ Unnamed Item ⋮ From a zoo to a zoology: Towards a general theory of graph polynomials ⋮ On the computational complexity of the Jones and Tutte polynomials ⋮ Complexity of approximating the vertex centroid of a polyhedron ⋮ Elements of a theory of simulation. II: Sequential dynamical systems. ⋮ Monomial bases for broken circuit complexes ⋮ Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph ⋮ Subtractive reductions and complete problems for counting complexity classes ⋮ A weighted graph polynomial from chromatic invariants of knots ⋮ \#P-completeness of counting update digraphs, cacti, and series-parallel decomposition method ⋮ The maximum clique problem
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
This page was built for publication: Hard Enumeration Problems in Geometry and Combinatorics
