Bax, Eric (1996) Recurrence-Based Reductions for Inclusion and Exclusion Algorithms Applied to P Problems. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechCSTR:1996.cs-tr-96-01
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_postscript.png)
|
Postscript
- Submitted Version
See Usage Policy. 2MB | |
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Submitted Version
See Usage Policy. 1MB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechCSTR:1996.cs-tr-96-01
Abstract
There are inclusion and exclusion algorithms for many #P problems. By imposing a hierarchy on the inclusion and exclusion formula's terms, we develop general reductions for inclusion and exclusion algorithms. We outline sufficient steps to tailor the general reductions to specific problems, and we ilustrate this process by applying it to algorithms for several #P problems. We test the reductions on the problem of counting Hamiltonian paths. Within the framework of the general reductions, we develop the concepts or zero sets and vestigial elements, and we present problem decomposition strategies. Also, we show how the reductions can be applied to algorithms that give approximate solutions to #P problems.
| Item Type: | Report or Paper (Technical Report) | ||||
|---|---|---|---|---|---|
| Additional Information: | © 1996 California Institute of Technology. January 23, 1996. I thank three great teachers at Furman University: Dr. Douglas Rall for introducing me to combinatorics and to research, Dr. P. M. Cook for listening and guidance, and Or. Hayden Porter for teaching me two concepts that are central to this work - recursion and abstraction. Thanks to Dr. Andras Recski at MTKI in Budapest for teaching me when I was a student there, and also for taking the time to read my papers and point me in useful directions when I walked into his office out of the blue several years later. I thank Dr. Joel Franklin for showing an interest in this work, for listening patiently as I tried to explain it, and for supplying just the right information at just the right time. I thank my advisor Dr. Yaser S. Abu-Mostafa for his support, advice, and example. Supported by an NSF fellowship. | ||||
| Group: | Computer Science Technical Reports | ||||
| Funders: |
| ||||
| Subject Keywords: | algorithms, combinatorial problems, parallel algorithms. | ||||
| Classification Code: | AMS subject classifications 05,68 | ||||
| DOI: | 10.7907/Z9ST7MVX | ||||
| Record Number: | CaltechCSTR:1996.cs-tr-96-01 | ||||
| Persistent URL: | https://resolver.caltech.edu/CaltechCSTR:1996.cs-tr-96-01 | ||||
| Usage Policy: | You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format. | ||||
| ID Code: | 26923 | ||||
| Collection: | CaltechCSTR | ||||
| Deposited By: | Imported from CaltechCSTR | ||||
| Deposited On: | 07 Mar 2002 | ||||
| Last Modified: | 03 Oct 2019 03:19 |
Repository Staff Only: item control page
