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 gra ... [truncated at 450 characters in length]
|Author||Farr, Graham E.;|
|Subject||Computational complexity Combinatorial enumeration problems Percolation (Statistical physics)|