Permanents, Pfaffian orientations, and even directed circuits (Q1971908): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: math/9911268 / rank | |||
Normal rank |
Latest revision as of 00:19, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Permanents, Pfaffian orientations, and even directed circuits |
scientific article |
Statements
Permanents, Pfaffian orientations, and even directed circuits (English)
0 references
23 March 2000
0 references
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.
0 references
Pfaffian orientations
0 references
permanent
0 references
determinant
0 references
Pólya matrix
0 references
characterization
0 references
polynomial-time algorithm
0 references