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 |