Thesis icon

Thesis

Topics in computational complexity

Abstract:

This thesis concerns the computational complexity of several combinatorial problems.

Chapter 1 is notation and definitions. In Chapter 2 the subgraph homeomorphism problem, for fixed pattern graphs H, is considered. For the cases H and#x2245; C6,C7,W4 or W5, we obtain exact characterizations of graphs with no subgraph homeomorphic from H, and derive efficient algorithms for recognizing such graphs. We then consider counting homeomorphs, and...

Expand abstract

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Role:
Author

Contributors

Role:
Supervisor
Role:
Supervisor
Publication date:
1986
Type of award:
DPhil
Level of award:
Doctoral
Awarding institution:
University of Oxford
Source identifiers:
603840078
Language:
English
Subjects:
UUID:
uuid:ad3ed1a4-fea4-4b46-8e7a-a0c6a3451325
Local pid:
td:603840078
Deposit date:
2012-05-08

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP