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

PhD Dissertation Defense Announcement by Md Zamilur Rahman:"Chordal Graphs and Their Relatives: Algorithms and Applications"

Monday, April 20, 2020 - 10:00 to 13:00

SCHOOL OF COMPUTER SCIENCE

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

Doctoral Dissertation by: Md Zamilur Rahman

 

Date: Monday April 20, 2020

Time: 10:00 am

Zoom Meeting: https://zoom.us/j/596511982   // Meeting ID: 596 511 982

Abstract:

While the problem of generating random graphs has received much attention, the problem of generating graphs for specific classes has not been studied much. In this dissertation, we propose schemes for generating chordal graphs, weakly chordal graphs, and strongly chordal graphs. We also present semi-dynamic algorithms for chordal graphs and strongly chordal graphs. As an application of a completion technique for chordal graphs, we also discuss a 1-round algorithm for approximate point placement in the plane in an adversarial model where the distance query graph presented to the adversary is chordal.

The proposed generation algorithms take the number of vertices, n, and the number of edges, m, as input and produces a graph in a given class as output. The generation method either starts with a tree or a complete graph. We then insert additional edges in the tree or delete edges from the complete graph. Our algorithm ensures that the graph properties are preserved after each edge is inserted or deleted. We have proposed algorithms to generate weakly chordal graphs and strongly chordal graphs from an arbitrary graph as input. In this case, we ensure the graph properties will be achieved on termination of the conversion process.

We have proposed a semi-dynamic algorithm for edge-deletion in a chordal graph. To the best of our knowledge, no study has been done for the problem of dynamic algorithms for strongly chordal graphs. To address this gap, we have also proposed a semi-dynamic algorithm for edge-deletions and a semi-dynamic algorithm for edge-insertions in strongly chordal graphs.

Keywords: chordal graph, weakly chordal graph, strongly chordal graph, graph generation, semi-dynamic algorithm

Thesis Committee:

Internal Reader: Dr. Dan Wu and Dr. Mehdi Kargar

External Reader: Dr. Fazle Baki

External Examiner: Dr. Anil Maheshwari

Advisors: Dr. Asish Mukhopadhyay and Dr. Yash Aneja

Chair: Dr. Andrea Sullivan-Clarke

PhD Dissertation Announcement

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