Polynomial time recognition and optimization algorithms on special classes of graphs

We present two algorithms that use newly developed tree data structures in their solutions. Our polynomial time recognition algorithm for probe interval graphs uses the MD-PQ tree to build a model of the graph. Our robust polynomial time algorithm for solving optimization problems on clique-width k graphs uses a k-HB tree to completely describe the construction of the graph. The tree is then used to solve the optimization problems.; To analyze a long sequence of DNA, restriction enzymes are used to cut the DNA strand into smaller fragments called clones. The clones are then reproduced many times for further research. To re-sequence the DNA strand, tests are performed to determine whether a pair of clones overlap in the longer DNA sequence. It is possible to avoid performing overlap tests on every pair of clones by selecting a subset of clones, called probes, and test for overlaps between two clones if and only if at least one of the clones is a probe. This procedure gives rise to a new graph theoretic model called the probe interval graph.; After studying the motivation behind earlier research in the recognition of probe interval graphs, we believed it was important to develop an algorithm that not only recognized the input graph, but also produced a model which could then be used to re-sequence the physical clones. The algorithms presented here have running times of O(n3) and O(n2).; Our second algorithm is the first robust, polynomial time optimization algorithm on clique-width k graphs. A graph with clique-width k has a corresponding clique-width k tree that completely describes the construction of the graph. The recognition of graphs in this class where k > 3 is open. Consequently, creating the corresponding clique-width k tree of G is open as well. Currently, there are linear time optimization problems on graphs with clique-width k provided that the clique-width k tree is given as input. Our robust algorithms require only an adjacency matrix as input.