CaltechAUTHORS
  A Caltech Library Service

A permanent formula with many zero-valued terms

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. https://resolver.caltech.edu/CaltechAUTHORS:20170408-163250714

[img] PDF - Accepted Version
See Usage Policy.

198Kb

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:
URLURL TypeDescription
http://dx.doi.org/10.1016/S0020-0190(97)00078-1DOIArticle
https://www.sciencedirect.com/science/article/pii/S0020019097000781PublisherArticle
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
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:03 Oct 2019 16:58

Repository Staff Only: item control page