Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


kent1208869783.pdf (170.97 KB)

ETD Abstract Container

Abstract Header

Finding A Maximum Clique of A Chordal Graph by Removing Vertices of Minimum Degree

Bhaduri, Sudipta
http://rave.ohiolink.edu/etdc/view?acc_num=kent1208869783

Abstract Details

2008, MS, Kent State University, College of Arts and Sciences / Department of Mathematical Sciences.
A graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. Chordal graphs are also called triangulated graphs. A graph is chordal if and only if it has a perfect elimination ordering. A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex v, v and neighbors of v that occur later than v in the order form a clique. In their paper Rose, Tarjan and Lueker have shown that a perfect elimination ordering of a chordal graph can be found efficiently using an algorithm lexicographic breadth first search. This algorithm maintains a partition of the vertices of the graph into a sequence of sets; initially this sequence consists of a single set with all vertices. The algorithm repeatedly chooses a vertex v from the earliest set in the sequence that contains previously not chosen vertices, and splits each set S of the sequence into two smaller subsets, the first consisting of the neighbors of v in S and the second consisting of the non-neighbors. When this splitting process is done for all the vertices, the sequence of the sets has one vertex per set, and is the reverse of a perfect elimination ordering. In his paper Fanica Gavril finds a maximum clique and a minimum coloring of a chordal graph using this perfect elimination ordering.In this paper, we will give an algorithm for finding a maximum clique of a chordal graph by removing vertices of minimum degree. We will also show how to color a chordal graph with minimum number of colors. We give a linear time algorithm to find a maximum clique of a chordal graph and also will show that the size of a maximum clique of a chordal graph equals the chromatic number of the graph, i.e., we can color the whole graph with the number of colors equal to the size of a maximum clique.
Feodor F. Dragan, Dr. (Advisor)
Johnnie W. Baker, Dr. (Committee Member)
Ruoming Jin, Dr. (Committee Member)
29 p.
Computer Science
Minimum Degree Ordering; M.D.O; Maximum Clique

Recommended Citations

Citations

  • Bhaduri, S. (2008). Finding A Maximum Clique of A Chordal Graph by Removing Vertices of Minimum Degree [Master's thesis, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1208869783

    APA Style (7th edition)

  • Bhaduri, Sudipta. Finding A Maximum Clique of A Chordal Graph by Removing Vertices of Minimum Degree. 2008. Kent State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=kent1208869783.

    MLA Style (8th edition)

  • Bhaduri, Sudipta. "Finding A Maximum Clique of A Chordal Graph by Removing Vertices of Minimum Degree." Master's thesis, Kent State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=kent1208869783

    Chicago Manual of Style (17th edition)

kent1208869783
3,261
© 2008, all rights reserved.
This open access ETD is published by Kent State University and OhioLINK.