Bax, Eric and Franklin, Joel (1997) A permanent formula with many zero-valued terms. Information Processing Letters, 63 (1). pp. 33-39. ISSN 0020-0190. doi:10.1016/S0020-0190(97)00078-1. https://resolver.caltech.edu/CaltechAUTHORS:20170408-163250714
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Accepted Version
See Usage Policy. 203kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170408-163250714
Abstract
Applying finite-differences to a generating function produces formulas for the permanent of a matrix. We present a setting of the finite-difference parameters for which the permanent formula has many zero-valued terms when applied to 0–1 matrices. We outline a method to reduce computation by eliminating sets of zero-valued terms and show that the method significantly increases the computation speed.
| Item Type: | Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| Additional Information: | © 1997 Published by Elsevier. Received 28 October 1996, Revised 28 February 1997. Communicated by D. Gries. We thank an anonymous referee and editor David Gries for advice regarding content and presentation. The first author thanks the second author for advice and guidance. | |||||||||
| Subject Keywords: | Algorithms; Combinatorial problems; #P; Permanent; Finite-difference; Generating function | |||||||||
| Issue or Number: | 1 | |||||||||
| Classification Code: | AMS subject classiffications 05,68 | |||||||||
| DOI: | 10.1016/S0020-0190(97)00078-1 | |||||||||
| Record Number: | CaltechAUTHORS:20170408-163250714 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170408-163250714 | |||||||||
| Official Citation: | Eric Bax, Joel Franklin, A permanent formula with many zero-valued terms, Information Processing Letters, Volume 63, Issue 1, 1997, Pages 33-39, ISSN 0020-0190, https://doi.org/10.1016/S0020-0190(97)00078-1. (http://www.sciencedirect.com/science/article/pii/S0020019097000781) | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 76205 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | 1Science Import | |||||||||
| Deposited On: | 07 Mar 2018 19:15 | |||||||||
| Last Modified: | 15 Nov 2021 16:58 |
Repository Staff Only: item control page
