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 AbstractThis 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.pdf239.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.