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