Counting linear extensions is #P-complete

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Counting linear extensions is #P-complete

Full text

Pdf (648 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 175 - 181

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Graham Brightwell	London School of Economics and Political Science, London, UK
Peter Winkler	Emory Univ., Atlanta, GA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 58, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/103418.103441 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M.D. Atkinson, Partial orders and comparison problems, Congressus Numerantium 47 (1985) 77-88.
	2	M.D. Atkinson and H.W. Chang, Extensions of partial orders of bounded width, Gongressus Numerantium 52 (1985) 21-35.
	3	M. D. Atkinson , H. W. Chang, Computing the number of mergings with constraints, Information Processing Letters, v.24 n.5, p.289-292, 16 March 1987 [doi>10.1016/0020-0190(87)90151-7]
	4	M. E. Dyer , A. M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM Journal on Computing, v.17 n.5, p.967-974, October 1988 [doi>10.1137/0217060]
	5	M. Dyer , A. Frieze, A random polynomial time algorithm for approximating the volume of convex bodies, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.375-381, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73043]
	6	J. Feigenbaum, private communication.
	7	P.C. Fishburn and W.V. Gehrlein, A comparative analysis of methods for constructing weak orders from partial orders, J. Math. Sociology 4 (1975) 93-102.
	8	M. Habib , R. H. Möhring, On some complexity properties of N-free posets and posets with bounded decomposition diameter, Discrete Mathematics, v.63 n.2-3, p.157-182, Feb. 1987 [doi>10.1016/0012-365X(87)90006-9]
	9	G.H. Hardy and E.M. Wright, An Introduction to the Theory oj Numbers, 4th Ed., Oxford University Press 1960.
	10	J. Kahn and M. Saks, BalaJlcing poser extensions, ORDER 1 No. 2 (1984) 113-126.
	11	A. Karzanov and L. Khachiyan, On the conductance of order Markov chains, Technical Report DCS TR 268, Rutgets University, June 1990.
	12	L. Kha#:hiyan, Complexity of polytope volume computation, Recent Progress in Discrete Computational Geometry, J. Pach eel., Springer-Verlag, to appear.
	13	H. Kierstead and W.T. Trotter, The number of depthfirst searches of an ordered set, ORDER, to appear.
	14	Nathan Linial, Hard enumeration problems in geometry and combinatorics, SIAM Journal on Algebraic and Discrete Methods, v.7 n.2, p.331-335, April 1986 [doi>10.1137/0607036]
	15	L. Lov#sz, An Algorithmic Theorp of Numbers, Graphs and Convezit# SIAM, Philadelphia 1986.
	16	S. Provan and M.O. Ball, On the complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Computing 12 (1983) 777-788.
	17	G. Steiner, Polynomial algorithms to count linear extensions in certain posets, Congressus Numemntium, to appear.
	18	G. Steiner, On counting constrained depth-first linear extensions of ordered sets, preprint.
	19	S. Toda, On the computational power of PP and +P, Proc. 30th IEEE Syrup. on Foundations of Computer Sci. ence (1989) 514-519.
	20	L.G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979) 189-201.
	21	L.G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8 (1979) 410-421.
	22	P. Winkler, Average height in a partially ordered set, Discrete Math. 39 (1982) 337-341.

CITED BY 8

	Paul D. Amer , Christophe Chassot , Thomas J. Connolly , Michel Diaz , Phillip Conrad, Partial-order transport service for multimedia and other applications, IEEE/ACM Transactions on Networking (TON), v.2 n.5, p.440-456, Oct. 1994
	Martin Charles Golumbic , Ron Shamir, Complexity and algorithms for reasoning about time: a graph-theoretic approach, Journal of the ACM (JACM), v.40 n.5, p.1108-1133, Nov. 1993
	Antti Ukkonen , Mikael Fortelius , Heikki Mannila, Finding partial orders from unordered 0-1 data, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Yiling Chen , Lance Fortnow , Nicolas Lambert , David M. Pennock , Jennifer Wortman, Complexity of combinatorial market makers, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Feng Chen , Traian Florin Serbanuta , Grigore Rosu, jPredictor: a predictive runtime analysis tool for java, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany
	Alfredo De Santis , Anna Lisa Ferrara , Barbara Masucci, New constructions for provably-secure time-bound hierarchical key assignment schemes, Theoretical Computer Science, v.407 n.1-3, p.213-230, November, 2008
	Constantinos Daskalakis , Richard M. Karp , Elchanan Mossel , Samantha Riesenfeld , Elad Verbin, Sorting and selection in posets, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.392-401, January 04-06, 2009, New York, New York
	Marília D. V. Braga , Marie-France Sagot , Celine Scornavacca , Eric Tannier, Exploring the Solution Space of Sorting by Reversals, with Experiments and an Application to Evolution, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.3, p.348-356, July 2008