Annals of Mathematics, II. Series, Vol. 150, No. 3, pp. 929-975, 1999

Outdated Archival Version

These pages are not updated anymore. For the current production of this journal, please refer to http://www.jstor.org/journals/0003486x.html.

Annals of Mathematics, II. Series
Vol. 150, No. 3, pp. 929-975 (1999)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home

EMIS Home

Permanents, Pfaffian orientations, and even directed circuits

Neil Robertson, P.D. Seymour and Robin Thomas

Review from Zentralblatt MATH:

The paper deals with the following problem asked by Pólya in 1913: Given a 0-1 matrix $A$, is there a matrix $B$ obtained from $A$ by changing signs of some $1$'s to $-1$'s so that the permanent of $A$ equals the determinant of $B$? Such $B$ is called a Pólya matrix for $A$. The paper provides a structural characterization of matrices for which Pólya's matrices exist. This characterization is used to construct a polynomial-time algorithm to decide whether a matrix has its Pólya matrix.

Reviewed by M.Truszczynski

Keywords: Pfaffian orientations; permanent; determinant; Pólya matrix; characterization; polynomial-time algorithm

Classification (MSC2000): 05C75 15A15 05C85 68Q25 68R10 05C70 05C38 05B20 05C20

Full text of the article:

PDF file (350 kilobytes)

Electronic fulltext finalized on: 8 Sep 2001. This page was last modified: 21 Jan 2002.

© 2001 Johns Hopkins University Press
© 2001--2002 ELibM for the EMIS Electronic Edition
Metadata extracted from Zentralblatt MATH with kind permission