JOIN US AT OPEN HOUSE MARCH 7

MSc Thesis Proposal Announcement by Sudiksha Khanduja:"Weakly chordal graphs: An Experimental Study "

Wednesday, January 22, 2020 - 11:00 to 13:00

SCHOOL OF COMPUTER SCIENCE

 

The School of Computer Science is pleased to present…

 

MSc Thesis Proposal by: Sudiksha Khanduja

 
Date: January 22, 2020
 
Time:  11 am – 1 pm
 
Location: Lambton Tower, Room 3105
 

Abstract:

 
Graph theory is an important field of study that enables one to get general ideas about graphs and their properties. It helps supply numerical information for enumerative problems and to provide a source from which specimen graphs can be taken for use in real-life problems. There are many situations (such as generating all linear layouts of weakly chordal graphs) where we want to generate instances of these to test algorithms for weakly chordal graphs. In my thesis we address the algorithmic problem of generating weakly chordal graphs. A graph G=(V, E), where V is the set of its vertices and E is the set of its edges, is called weakly chordal graph, if neither G nor its complement contains an induced chordless cycle on five or more vertices.
 
Our work is in two parts. In the first part, we carry out a comparative study of two existing algorithms for generating weakly chordal graphs. A pair {u, v} of nonadjacent vertices in G form a 2-pair if every chordless path between u and v is of length two. The first algorithm for generating weakly chordal graphs, repeatedly finds a 2-pair and adds an edge between them. The second generation algorithm starts by constructing a tree and then generates an orthogonal layout (which is a weakly chordal graph on the n vertices) based on this tree. Edges are then inserted into this orthogonal layout till there are m edges. The output graphs from these two methods are compared with respect to several parameters like number of four cycles, the number of non 2-pairs in the graphs generated by the second method.
 
In the second part, we propose an algorithm for generating weakly chordal graphs by edge deletions from a complete graph. The algorithm starts with a complete graph to generate a weakly chordal graph. The algorithm iterates by preventing a hole or an antihole configuration being created for every successful deletion of an edge.
 
 
 

Thesis Committee:

 
Internal Reader: Dr. Dan Wu
 
External Reader: Dr. Yash Anjea
 
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