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