On the Magnification of Exchange Graphs with Applications to Enumeration Problems (Thesis)

TitleOn the Magnification of Exchange Graphs with Applications to Enumeration Problems (Thesis)
Publication TypeTechnical Report
Year of Publication1990
AuthorsDagum P
Other Numbers594
Abstract

This thesis concerns the design of fully polynomial approximation algorithms for some #P-complete enumeration problems. The types of enumeration problems we consider can be regarded as instances of computing |F| for set systems (V,F) having a description in terms of a "complete set of implicants" I with |I| = O(|V| superscript 2). By studying the geometric quantities of adjacency and magnification of the "exchange graph" of set systems, we establish criteria for the design of fully polynomial algorithms.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-90-030.pdf
Bibliographic Notes

ICSI Technical Report TR-90-030

Abbreviated Authors

P. Dagum

ICSI Publication Type

Technical Report