Algorithms for some special graphs

Graphs play an important role in modeling real-world problems. In particular, some special intersection graphs such as interval graphs, circular-arc graphs and permutation graphs have a broad range of applications in computer science, operations research, and engineering. Some fundamental graph problems such as finding connected components, biconnected components, depth-first search trees, etc., can be solved more efficiently for these special graphs than in general graphs by exploiting certain properties of the special graphs. Some optimization problems such as finding independent set, dominating set, and Hamiltonian circuit are all known to be NP-complete for a general graph. When, however, we restrict the graph to these special classes of the intersection graph, many of these problems fall into the P class. In this dissertation, we study some efficient serial and parallel algorithms for solving the problems such as finding biconnected components, depth-first search trees, all maximum weight dominating sets and minimum weight dominating set in interval graphs, circular-arc graphs and permutation graphs.