Parallel Algorithms for Graph Problems
Xin He Principal Investigator
MetadataShow full item record
Due to the constraints of parallel computation environment, efficient parallel algorithms often drastically differ from their sequential counterparts. The study of parallel computation often leads to the discovery of new properties of the problem being solved. Therefore the study of parallel algorithms is particularly fruitful for the graphs having special properties. This research develops efficient parallel algorithms for the following classes of special graphs: cographs, permutation graphs, comparability graphs, and planar graphs. These graph problems find broad applications in computer science. The sequential algorithms for solving them have been extensively studied. However, it appears difficult to solve them in parallel. The research is focused on the discovery of new properties of these graphs that can be use in designing efficient parallel algorithms. In addition to design efficient algorithms for specific problems, new techniques that can be used for solving more general problems are developed.