The University of Windsor is preparing for a safe return to campus. Learn More.

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

Thursday, January 23, 2020 - 13:30 to 15:30
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


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