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. SeriesVol. 150, No. 3, pp. 929-975 (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 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:
Electronic fulltext finalized on: 8 Sep 2001. This page was last modified: 21 Jan 2002.
© 2001 Johns Hopkins University Press
|