SIAM Journal on Algebraic and Discrete Methods · 1986 · 132 citations · 7 references
Natural SciencesComputer ScienceMathematicsCombinatoricsDiscrete MathematicsGeometryCombinatorial EnumerationDiscrete GeometryEnumerative CombinatoricsEnumeration Algorithms For GraphsEnumeration Of Combinatorial ClassesEnumerative Graph TheoryGraph EnumerationOrientationsPolytope Enumeration
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.
7
The complexity of computing the permanent
Leslie G. Valiant · Theoretical Computer Science · 1979 · 2.8K citations
The Complexity of Enumeration and Reliability Problems
Leslie G. Valiant · SIAM Journal on Computing · 1979 · 2.1K citations
Acyclic orientations of graphs
Richard P. Stanley · Discrete Mathematics · 1973 · 445 citations