Thesis
The complexity of counting problems
- Abstract:
-
This thesis is concerned with the computational complexity of several counting problems occurring in graph theory, all of which are related directly to the Tutte polynomial. The Tutte polynomial contains as specialisations many fundamental quantities. Among these are the partition function of the Ising and Potts models on the graph and the reliability probability as well as basic combinatorial functions such as the chromatic and flow polynomials.
Polynomial-time computable recurrence...
Expand abstract
Actions
Bibliographic Details
- Publication date:
- 1994
- Type of award:
- DPhil
- Level of award:
- Doctoral
- Awarding institution:
- University of Oxford
Item Description
- Language:
- English
- Subjects:
- UUID:
-
uuid:52070098-14fa-4cf1-ae6e-9f9ce6a626d8
- Local pid:
- td:603835633
- Source identifiers:
-
603835633
- Deposit date:
- 2012-05-08
Terms of use
- Copyright holder:
- Annan, James
- Copyright date:
- 1994
- Notes:
- The digital copy of this thesis has been made available thanks to the generosity of Dr Leonard Polonsky
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record