Permanents, Pfaffian orientations, and even directed circuits

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

Permanents, Pfaffian orientations, and even directed circuits

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

Mathematics

Research output: Contribution to journal › Conference article › peer-review

35 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 language	English (US)
Pages (from-to)	402-405
Number of pages	4
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
State	Published - 1997
Event	Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA Duration: May 4 1997 → May 6 1997

All Science Journal Classification (ASJC) codes

Software

Cite this

@article{44c1ae5234064db4b30ae00fddbe0907,

title = "Permanents, Pfaffian orientations, and even directed circuits",

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.",

author = "William McCuaig and Neil Robertson and Seymour, {P. D.} and Robin Thomas",

year = "1997",

language = "English (US)",

pages = "402--405",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing ; Conference date: 04-05-1997 Through 06-05-1997",

}

TY - JOUR

T1 - Permanents, Pfaffian orientations, and even directed circuits

AU - McCuaig, William

AU - Robertson, Neil

AU - Seymour, P. D.

AU - Thomas, Robin

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030699601&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030699601&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0030699601

SN - 0734-9025

SP - 402

EP - 405

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing

Y2 - 4 May 1997 through 6 May 1997

ER -

Permanents, Pfaffian orientations, and even directed circuits

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this