On Complexity of Computing the Permanent of a Rectangular Matrix

Tsutomu KAWABATA; Jun TARUI

Copy

Tsutomu KAWABATA, Jun TARUI, "On Complexity of Computing the Permanent of a Rectangular Matrix" in IEICE TRANSACTIONS on Fundamentals, vol. E82-A, no. 5, pp. 741-744, May 1999, doi: .
Abstract: We show that the permanent of an m n rectangular matrix can be computed with O(n 2^m 3^m) multiplications and additions. Asymptotically, this is better than straightforward extensions of the best known algorithms for the permanent of a square matrix when m/n log₃ 2 and n .
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_5_741/_p

Copy

@ARTICLE{e82-a_5_741,
author={Tsutomu KAWABATA, Jun TARUI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On Complexity of Computing the Permanent of a Rectangular Matrix},
year={1999},
volume={E82-A},
number={5},
pages={741-744},
abstract={We show that the permanent of an m n rectangular matrix can be computed with O(n 2^m 3^m) multiplications and additions. Asymptotically, this is better than straightforward extensions of the best known algorithms for the permanent of a square matrix when m/n log₃ 2 and n .},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - On Complexity of Computing the Permanent of a Rectangular Matrix
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 741
EP - 744
AU - Tsutomu KAWABATA
AU - Jun TARUI
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1999
AB - We show that the permanent of an m n rectangular matrix can be computed with O(n 2^m 3^m) multiplications and additions. Asymptotically, this is better than straightforward extensions of the best known algorithms for the permanent of a square matrix when m/n log₃ 2 and n .
ER -