RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1997 Volume 9, Issue 3, Pages 96–100 (Mi dm484)

Polynomial algorithms for computing the permanents of some matrices

A. P. Il'ichev, G. P. Kogan, V. N. Shevchenko


Abstract: Let $B_n$ be the matrix whose columns are all $n$-dimensional non-zero Boolean vectors and let $B_{nk}$ be the matrix whose columns are all $n$-dimensional Boolean vectors with $k$ unities. We suggest polynomial with respect to $n$ algorithms to compute the permanents of these matrices and some related matrices. These algorithms are based on the generating functions for values of permanents of the matrices under consideration.

UDC: 519.7

Received: 08.11.1994

DOI: 10.4213/dm484


 English version:
Discrete Mathematics and Applications, 1997, 7:4, 413–417

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024