MSc Thesis Proposal Announcement by Aayushi Srivastava:"Minimal Triangulations: An Experimental Study"

Thursday, January 23, 2020 - 13:30 to 15:30
SCHOOL OF COMPUTER SCIENCE
 
The School of Computer Science is pleased to present…
 
MSc Thesis Proposal by: Aayushi Srivastava
 
 
 
Date: 23-01-2020
 
Time:  1:30-3:30 pm
 
Location: Lambton Tower Room 3105
 

Abstract:

 
Graph generation enables one to get a general idea about graphs and their properties. Graph theory is used for real-life problems where it helps provide numerical information for enumerative problems and is the source from which specimen graphs can be generated for problems where a theoretical solution is not present. Graph generation mechanisms can be used to generate test instances for other algorithms. An undirected graph is chordal if every cycle of length greater than three has a chord: namely an edge connecting two non-consecutive vertices on the cycle. A chordal graph is the class of graph nearest to a tree for which generation techniques are well-explored. We exploit the properties of chordal graphs that follow from the well-known fact that chordal graphs admit tree representations. Thus, its generation is pretty much similar to the trees. Several important and widely studied problems on graphs are concerned with computing an embedding of an arbitrary graph into a chordal graph. Edges can be added to any arbitrary graph, called a triangulation of the input graph, which is chordal. Generating a chordal graph from an arbitrary graph can be done by turning any vertex ordering into a perfect elimination order by adding edges. In minimal triangulation, the edges added are inclusion minimal set of edges. While minimum triangulation requires the set of edges of the smallest size. LB-Triangulation is an algorithm to generate minimal triangulation but the edges added can be far from minimum. Minimum Degree Vertex algorithm is a widely used heuristic which is an approximation for minimum triangulation. It is relevant in the area of applications including sparse matrix computations, database management, knowledge-based systems, and computer vision. A comparative study is done between LB-Triangulation and Minimum Degree Vertex using Maximum Cardinality Search based on triangulation.  We exploited the reduction method to generate chordal graphs from bipartite graphs, adding a minimal number of edges. We also modified a method of Dirac for the generation of k-Chromatic chordal graphs by adding fewest possible edges. For vertex coloring, we used an algorithm named Welsch-Powell. The minimum fill-in problem has been shown to be NP-complete by reduction from the problem of finding a minimum number of edges to be added to a bipartite graph to turn it into a chain graph. A graph is nearly chordal if for every vertex the induced subgraph of its non-neighbors is chordal.  We are also studying the problem generating nearly chordal graphs and subsequently generate chordal graphs form these by adding as few edges as possible.
 

Thesis Committee:

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

MSc Thesis Proposal Announcement

 

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