Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


osu1229459765.pdf (3.33 MB)

ETD Abstract Container

Abstract Header

Graph Coloring and Clustering Algorithms for Science and Engineering Applications

Bozdag, Doruk
http://rave.ohiolink.edu/etdc/view?acc_num=osu1229459765

Abstract Details

2008, Doctor of Philosophy, Ohio State University, Electrical and Computer Engineering.
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.
Umit Catalyurek, PhD (Advisor)
Füsun Özgüner, PhD (Advisor)
Charles Klein, PhD (Committee Member)
179 p.
Bioinformatics; Computer Science; Electrical Engineering
parallel graph coloring; distributed memor; y biclustering; co-clustering; subspace clustering

Recommended Citations

Citations

  • Bozdag, D. (2008). Graph Coloring and Clustering Algorithms for Science and Engineering Applications [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1229459765

    APA Style (7th edition)

  • Bozdag, Doruk. Graph Coloring and Clustering Algorithms for Science and Engineering Applications. 2008. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1229459765.

    MLA Style (8th edition)

  • Bozdag, Doruk. "Graph Coloring and Clustering Algorithms for Science and Engineering Applications." Doctoral dissertation, Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1229459765

    Chicago Manual of Style (17th edition)

osu1229459765
2,453
© 2008, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.