A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-07222011-120507


Type of Document Master's Thesis
Author Bonnin Cadogan, Jose M
URN etd-07222011-120507
Title A generalization of chordal graphs
Degree Master of Science
Department Computer Science
Advisory Committee
Advisor Name Title
Jeremy Spinrad Committee Member
Mark Ellingham Committee Member
Keywords
  • np-completeness
  • maximum independent set problem
  • chordal graphs
  • greedy algorithms
Date of Defense 2011-07-22
Availability unrestricted
Abstract
This thesis introduces graph class C, a recognition algorithm for graphs in the class, and shows that some problems are NP-complete on the class. Class C is a generalization of chordal graphs. Informally, a graph is in class C if successively removing the neighborhoods of its simplicial vertices produces a null graph. More precisely, a graph G is in class C if G is the null graph or G contains a simplicial vertex v such that G - N[v] is in C. A greedy algorithm can recognize whether a graph is in class C in O(nm) time. The maximum independent set problem and the clique cover problem on class C can be solved in linear time using greeedy algorithms. However, the maximum clique problem and the coloring problem are NP-complete on the class.

This work also examines class K, the class of graphs in class C whose complements are also in class C, and shows that the maximum weighted independent set problem is NP-complete on the class. Class K generalizes split graphs, the class of graphs that are chordal and co-chordal. The four problems mentioned in relation to class C can be solved in linear time on class K using greedy algorithms. The same is known to be true for split graphs. However, while the maximum weighted independent set problem can be solved in polynomial time on split graphs, this problem is NP-complete on class K.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Bonnin.pdf 239.56 Kb 00:01:06 00:00:34 00:00:29 00:00:14 00:00:01

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LITS.