Hard Enumeration Problems in Geometry and Combinatorics

1986/04/01 by Nathan Linial · 5 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Class (philosophy) #Combinatorics #Computational Geometry and Mesh Generation #Discrete mathematics #Enumeration #Enumerative combinatorics #Graph #Mathematics #Polytope #graph theory and CDMA systems

paper · doi:10.1137/0607036

openalex publication_date 1986/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/04

Abstract

A number of natural enumeration problems in geometry and combinatorics are shown to be complete in the class # P introduced by Valiant. Among others this is established for the numeration of vertices and of facets of a polytope, acyclic orientations of a graph and satisfying assignments of implicative boolean formulas.

Citations

• The complexity of computing the permanent
• Acyclic orientations of graphs
• The Complexity of Enumeration and Reliability Problems

Cited by

• The Computational Complexity of the Tutte Plane: the Bipartite Case
• On enumerating all minimal solutions of feedback problems
• A Survey of Combinatorial Gray Codes
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Chromatic polynomial [wikipedia]