Computing permanents via determinants for some classes of sparse matrices (Q852624)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5072848
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Computing permanents via determinants for some classes of sparse matrices |
scientific article; zbMATH DE number 5072848 |
Statements
Computing permanents via determinants for some classes of sparse matrices (English)
0 references
15 November 2006
0 references
\textit{B. Codenotti} and \textit{G. Resta} [Linear Algebra Appl. 355, No. 1--3, 15--34 (2002; Zbl 1017.65044)] have given a formula expressing the permanent of a circulant \((0,1)\) matrix with only 3 or 4 ones per row as the sum of only few determinants. The analysis is based on the bipartite graph that is associated with the given matrix. Only few determinants need to be computed if the graph is embeddable in a surface of low genus (1 or 2). It is shown in this paper that the latter property can hold for certain \((0,1)\) matrices that may not be circulant.
0 references
sparse circulant matrix
0 references
matrix permanent
0 references
\((0,1)\) matrix
0 references
bipartite graph
0 references
0.9007067680358887
0 references
0.8823422193527222
0 references
0.8636638522148132
0 references
0.8636638522148132
0 references
