Permanents, Pfaffian orientations, and even directed circuits (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Permanents, Pfaffian orientations, and even directed circuits (extended abstract)

Full text

Pdf (572 KB)

Source

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

El Paso, Texas, United States

Pages: 402 - 405

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

William McCuaig	5268 Eglinton St., Burnaby, B.C., Canada V5G 2B2
Neil Robertson	Department of Mathematics, Ohio State University, 231 W. N3th Ave., Columbus, Ohio
P. D. Seymour	Bellcore, 445 South St., Morristown, New Jersey
Robin Thomas	School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 13, Citation Count: 6

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/258533.258625 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	R. A. Brualdi and B. L. Shader, Matrices of signsolvable linear systems, Cambridge Tracts in Math ematics 116 (1995).
	2	J. E. Hopcroft and R. M. Karp, An n5/2 algorithm for maximum matchings in bipartite graphs, SIAM J. Comput. 2 (1973), 225-231.
	3	P.W. Kasteleyn, Dimer statistics and phase transitions, J. Math. Phys. 4 (1963), 287-293.
	4	P.W. Kasteleyn, Graph theory and crystal physics Graph Theory and Theoretical Physics (F. Harary ed.), Academic Press, New York, 1967, 43-110.
	5	V. Klee, R. Ladner and R. Manber, Sign-solvability. revisited, Linear Algebra Appl. 59 (1984), 131- 158.
	6	L. Lov&sz and M. Plummer, Matching theory, Annals of Discrete Math. 29, North-Holland, Amsterdam, New York, Oxford, Tokyo 1986.
	7	N. Robertson, P. D. Seymour and R. Thomas, Permanents, Pfa~ orientations, and even directed circuits, manuscript.
	8	P. D. Seymour, On the two-colouring of hypergraphs, Quart. J. Math. Oxford 25 (1974), 303- 312.
	9	Paul Seymour , Carsten Thomassen, Characterization of even directed graphs, Journal of Combinatorial Theory Series B, v.42 n.1, p.36-45, Feb. 1987 [doi>10.1016/0095-8956(87)90061-X]
	10	C. Thomassen, Even cycles in directed graphs, European J. Combin. 6 (1985), 85-89.
	11	C. Thomassen, Sign-nonsingular matrices and even cycles in directed graphs, Linear Algebra and Appl. 75 (1986), 27-41.
	12	C. Thomassen, The even cycle problem for directed graphs, J. Amer. Math. Soc. 5 (1992), 217-229.
	13	Carsten Thomassen, The even cycle problem for planar digraphs, Journal of Algorithms, v.15 n.1, p.61-75, July 1993 [doi>10.1006/jagm.1993.1030]
	14	L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), 189- 201.
	15	V. V. Vazirani , M. Yannakakis, Pfaffian orientations 0-1 permanents, and even cycles in directed graphs, Discrete Applied Mathematics, v.25 n.1-2, p.179-190, 1989 [doi>10.1016/0166-218X(89)90053-X]

CITED BY 6

	Weigen Yan , Fuji Zhang, Enumeration of perfect matchings of a type of Cartesian products of graphs, Discrete Applied Mathematics, v.154 n.1, p.145-157, 1 January 2006
	David P. Jacobs , Robert E. Jamison , Alice A. McRae, On the complexity of sign-nonsingularity and equal unions of sets, Proceedings of the 38th annual on Southeast regional conference, April 07-08, 2000, Clemson, South Carolina
	Rajneesh Hegde, Finding 3-shredders efficiently, ACM Transactions on Algorithms (TALG), v.2 n.1, p.14-43, January 2006
	Serguei Norine , Robin Thomas, Generating bricks, Journal of Combinatorial Theory Series B, v.97 n.5, p.769-817, September, 2007
	Weigen Yan , Fuji Zhang, A quadratic identity for the number of perfect matchings of plane graphs, Theoretical Computer Science, v.409 n.3, p.405-410, December, 2008
	Dong Ye , Heping Zhang, 2-extendability of toroidal polyhexes and Klein-bottle polyhexes, Discrete Applied Mathematics, v.157 n.2, p.292-299, January, 2009