Permanents, Pfaffian orientations, and even directed circuits

William McCuaig, Neil Robertson, P. D. Seymour, Robin Thomas

Research output: Contribution to journalConference article

23 Scopus citations

Abstract

We give a polynomial-time algorithm for the following problem of Polya. Given an n×n 0-1 matrix, either find a matrix obtained from it by changing some of the 1's to -1's in such a way that the determinant of the new matrix equals the permanent of the old one, or determine that no such matrix exists. This is equivalent to finding Pfaffian orientations of bipartite graphs and to the even circuit problem for directed graphs. The algorithm is based on a structural characterization of bipartite graphs that admit a Pfaffian orientation.

Original languageEnglish (US)
Pages (from-to)402-405
Number of pages4
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Jan 1 1997
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Permanents, Pfaffian orientations, and even directed circuits'. Together they form a unique fingerprint.

  • Cite this