The University of Windsor has moved to an “essential service only” model. Learn More.

MSc Thesis Defense of Aayushi Srivastava:"Generating Chordal Graphs with few Fill-in Edges"

Wednesday, May 20, 2020 - 13:00 to 14:30

SCHOOL OF COMPUTER SCIENCE

 

The School of Computer Science is pleased to present…

 
MSc Thesis Defense by: Aayushi Srivastava
 
Date:  Wednesday May 20, 2020
 
Time: 1:00 pm – 2:30 pm
 
Zoom meeting url:     https://zoom.us/j/91893427510?
 

Abstract:

 
Graph Generation aids in analysis of graphs and their properties while insinuating conjectures via counterexamples and even generating test instances for other algorithms. Any given graph can be embedded in a chordal graph by adding edges, and the resulting chordal graph is called a triangulation of the input graph i.e., contains no induced chordless cycle on four or more vertices. We exploit the properties of chordal graphs that follow from the well-known fact that chordal graphs admit tree representations. Triangulation involves turning any vertex ordering into a perfect elimination order by adding edges and is categorized as Minimal and Minimum. In minimal triangulation, the edges added are inclusion minimal set of edges. While minimum triangulation requires the set of edges to be of the smallest size. We have compared three such algorithms based on the fill-in edges and run time. Two of which namely LB-Triangulation and Lex-M perform minimal triangulation while Minimum Degree Vertex heuristic is an approximation for Minimum Triangulation. We exploited the reduction method to generate chordal graphs from bipartite graphs, adding a minimal number of edges and represent minimum triangulation as NP-Complete for bipartite graphs using chain graphs. We conducted a Comparative study based on fill-in edges and run time on Bipartite graphs using Reduction method and Minimum Degree Vertex heuristic. We also modified Dirac's Method of generation of K-Chromatic Chordal graphs using as few edges as possible and did minimum vertex coloring.
 
A graph is nearly chordal if for every vertex the induced subgraphs of its non-neighbors is chordal. We devised an algorithm to generate nearly chordal graphs and have provided a recognition algorithm to identify such graphs. A graph G= (V, E), is called weakly chordal, if neither G, nor its complement G’, contains an induced chordless cycle on five or more vertices. We have studied and established the relationship between chordal, nearly chordal and weakly chordal graphs in the thesis.
 
Keywords: Triangulation, Chordal Graph, Bipartite graph, Nearly Chordal Graph, Fill-in Problem
 

Thesis Committee:

 
Internal Reader: Dr. Dan Wu      
 
External Reader: Dr. Yash Aneja
 
Advisor:  Dr. Asish Mukhopadhyay
 
Chair: Dr. Xiaobu Yuan

MSc Thesis Defense Announcement

 

 

 5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716 csgradinfo@uwindsor.ca

 

 

 

5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716 csgradinfo@uwindsor.ca