JOIN US AT OPEN HOUSE MARCH 7

PhD Seminar Announcement by Md Zamilur Rahman:"A Separator-based Method for Generating Weakly Chordal Graphs"

Friday, November 15, 2019 - 10:00 to 12:00

SCHOOL OF COMPUTER SCIENCE

 

The School of Computer Science at the University of Windsor is pleased to present …

 
PhD. Seminar by: 
Md Zamilur Rahman
 
Date: Friday, November 15, 2019
Time: 10:00am
Location: Essex Hall Room 109
 
Abstract:
A graph G is chordal if it has no chordless cycles of size four or more. However, the complement of a chordal graph G can contain an induced chordless cycle of size four. The complement cannot contain a five cycle, as the complement of a five cycle is also a five cycle. This suggests the generalization of chordal graphs to weakly chordal (or weakly triangulated) graphs as those graphs G such that neither G nor its complement G¯ contains induced chordless cycles of size five or greater. From the symmetry of the definition it follows that G¯ is also weakly chordal. The problem of generating graphs uniformly at random has received much attention but little is known about the problem of generating weakly chordal graphs. 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 this talk we address the algorithmic problem of generating weakly chordal graphs. 
We propose a scheme for generating a weakly chordal graph on n vertices with m edges. In this method, we first construct a tree and then generate an orthogonal layout (which is a weakly chordal graph on the n vertices) based on this tree. We then insert additional edges, if needed, for a total of m edges. Our algorithm ensures that the graph remains weakly chordal after each edge is inserted. The time complexity of an insertion query is O(du2dv2(n+m)), where du and dv are the degrees of the vertices u and v we want to join with an edge and an insertion takes constant time. The advantages of this method are that it uses very simple data structures and exploits the basic structural properties of a weakly chordal graph.

 

Thesis Committee: 

Internal Reader: Dr. Dan Wu and Dr. Mehdi Kargar
External Reader: Dr. Fazle Baki
Advisor: Dr. Asish Mukhopadhyay and Dr. Yash Aneja

 

PhD Seminar Announcement

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