On the Magnification of Exchange Graphs with Applications to Enumeration Problems (Thesis)
Title | On the Magnification of Exchange Graphs with Applications to Enumeration Problems (Thesis) |
Publication Type | Technical Report |
Year of Publication | 1990 |
Authors | Dagum, P. |
Other Numbers | 594 |
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. |
URL | http://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 |