Skip to Main Content
 

Global Search Box

 
 
 

ETD Abstract Container

Abstract Header

Analysis of Algorithms for Star Bicoloring and Related Problems

Jones, Jeffrey S.
http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1426770501

Abstract Details

2015, Doctor of Philosophy (PhD), Ohio University, Computer Science (Engineering and Technology).
This dissertation considers certain graph-theoretic combinatorial problems which have direct application to the efficient computation of derivative matrices (“Jacobians”) which arise in many scientific computing applications. Specifically, we analyze algorithms for Star Bicoloring and establish several analytical results. We establish complexity-theoretic lower bounds on the approximability of algorithms for Star Bicoloring, showing that no such polynomial-time algorithm can achieve an approximation ratio of O(N ^(1/3)-e ) for any e > 0 unless P = NP. We establish the first algorithm (ASBC) for Star Bicoloring with a known approximation upper-bound, showing that ASBC is an O(N ^(2/3 )) polynomial-time approximation algorithm. Based on extension of these results we design a generic framework for greedy Star Bicoloring, and implement several specific methods for comparison. General analysis techniques are developed and applied to both algorithms from the literature (CDC, Hossain and Steihaug, 1998 [1]) as well as those developed as part of the framework. We provide numerous approximability results including the first approximation analysis for the CDC algorithm, showing that CDC is an O(N ^(3/4) ) approximation algorithm. Finally, we observe that all algorithms within this generic framework produce a restricted class of star bicolorings that we refer to as Distance-2 Independent Set Colorings (D2ISC). We establish the relationship between Star Bicoloring and D2ISC. In particular we show that these two notions are not equivalent, that D2ISC is NP-complete and that it cannot be approximated to within O(N ^(1/3 -e) ) for any e > 0 unless P = NP.
David Juedes, Ph.D. (Advisor)
Razvan Bunescu, Ph.D. (Committee Member)
Frank Drews, Ph.D. (Committee Member)
Cynthia Marling, Ph.D. (Committee Member)
Sergio Lopez, Ph.D. (Committee Member)
Howard Dewald, Ph.D. (Committee Member)
172 p.
Applied Mathematics; Computer Science
star bicoloring; acyclic bicoloring; Jacobian matrix computation; approximation algorithms; greedy star bicoloring; Jacobian matrix optimization; greedy optimization methods

Recommended Citations

Citations

  • Jones, J. S. (2015). Analysis of Algorithms for Star Bicoloring and Related Problems [Doctoral dissertation, Ohio University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1426770501

    APA Style (7th edition)

  • Jones, Jeffrey. Analysis of Algorithms for Star Bicoloring and Related Problems. 2015. Ohio University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1426770501.

    MLA Style (8th edition)

  • Jones, Jeffrey. "Analysis of Algorithms for Star Bicoloring and Related Problems." Doctoral dissertation, Ohio University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1426770501

    Chicago Manual of Style (17th edition)

ohiou1426770501
592
© 2015, all rights reserved.
This open access ETD is published by Ohio University and OhioLINK.