Publication Details

Title: On the Magnification of Exchange Graphs with Applications to Enumeration Problems (Thesis)
Author: P. Dagum
Bibliographic Information: ICSI Technical Report TR-90-030
Date: July 1990
Research Area: [Research Area not defined]
Type: Technical Reports
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-030.pdf

Overview:
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.

Bibliographic Reference:
P. Dagum. On the Magnification of Exchange Graphs with Applications to Enumeration Problems (Thesis). ICSI Technical Report TR-90-030, July 1990