Permanents, Pfaffian orientations, and even directed circuits (Q1971908)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Publication:1971908 |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8770940899848938
0 references
0.8469404578208923
0 references
0.8043606281280518
0 references
