On Complexity of Computing the Permanent of a Rectangular Matrix (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
We show that the permanent of an m×n rectangular matrix can be computed with O (n2^m+3^m) multiplications and additions. Asymptotically, this is better than straight forward extensions of the best known algorithms for the permanent of a square matrix when m/n < log_3 2 and n→∝.
- 社団法人電子情報通信学会の論文
- 1999-05-25
著者
-
Kawabata Tsutomu
Department Of Information And Communication Engineering University Of Electro-communications
-
Kawabata Tsutomu
Department Of Communications And Systems Engineering University Of Electro-communications
-
TARUI Jun
Department of Communications and Systems Engineering, University of Electro-Communications
-
Tarui Jun
Department Of Communications And Systems Engineering University Of Electro-communications
-
Kawabata Tsutomu
Department Of Communication Engineering And Informatics The University Of Electro-communications
関連論文
- Videothoracoscopic Surgery for Thoracic Neurogenic Tumors : A 7-Year Experience
- Endobronchial Metastasis from Renal Cell Carcinoma : Report of a Case
- Analysis of Zero-Redundancy Estimator with a Finite Window for Markovian Source(Information Theory, Information Theory and Its Applications)
- Enumerating the Uniform Switching System by K-Sets (Special Section on Discrete Mathematics and Its Applications)
- Improvement of Upper Bound to the Optimal Average Cost of the Variable Length Binary Code (Special Section on Information Theory and Its Applications)
- On Complexity of Computing the Permanent of a Rectangular Matrix (Special Section on Discrete Mathematics and Its Applications)
- Novel Approach for a Pulmonary Bronchogenic Cyst : A Report of a Case
- Constructing Families of ε-Approximate k-Wise Independent Permutations(Discrete Mathematics and Its Applications)
- Level-Crossing Problem of a Gaussian Process Having Gaussian Power Spectrum Density
- On the distribution densities of capacity fade and inter-fade time intervals over SISO Rayleigh mobile fading channels
- A Post-Processing for the Enumerative Code Implementation of Ziv-Lempel Incremental Parsing(Fundamental Theories for Communications)
- A Capacity Formula for Multi-Input Erasure Channel(Information Theory and Its Applications)
- A Phenomenological Study on Threshold Improvement via Spatial Coupling