Graph coloring and clustering algorithms for science and engineering applications

In this dissertation, efficient algorithms are proposed for two important combinatorial problems in science and engineering applications: parallel graph coloring and subspace clustering. For parallel distance-1 and distance-2 coloring problems, a framework that unifies several existing techniques for creating or facilitating concurrency are presented for distributed-memory computers. Extensions for similar graph and hypergraph coloring problems are also described. Through extensive set of experiments, the algorithms are shown to be efficient and scalable. In addition, new algorithms are proposed for particular instances of subspace clustering problem. A generalized cluster pattern model is introduced to discover complex relationships in large datasets and a search algorithm that utilizes established techniques from related combinatorial problems is designed to solve this problem. Also, biclustering, a special case of subspace clustering, is considered and a new biclustering algorithm is proposed to identify co-regulated genes in large gene expression datasets. The algorithm is the first one to utilize a well known statistical correlation measure in biclustering context. In order to extract useful correlation information from multiple gene expression datasets, a novel method is introduced as well. Both subspace clustering and biclustering algorithms are shown to perform well at identifying targeted relationships in large datasets. The biclustering algorithm is also applied on real gene expression datasets and returned promising clustering results.