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. 929975 (1999) 

Permanents, Pfaffian orientations, and even directed circuitsNeil Robertson, P.D. Seymour and Robin ThomasReview from Zentralblatt MATH: The paper deals with the following problem asked by Pólya in 1913: Given a 01 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 polynomialtime algorithm to decide whether a matrix has its Pólya matrix. Reviewed by M.Truszczynski Keywords: Pfaffian orientations; permanent; determinant; Pólya matrix; characterization; polynomialtime algorithm Classification (MSC2000): 05C75 15A15 05C85 68Q25 68R10 05C70 05C38 05B20 05C20 Full text of the article:
Electronic fulltext finalized on: 8 Sep 2001. This page was last modified: 21 Jan 2002.
© 2001 Johns Hopkins University Press
