Site Search
Computer Science


Alioune Ngom, Ph.D.Dr. Alioune Ngom
Dr. Alioune Ngom
Lambton TowerLambton Tower
Lambton Tower
Windsor WaterfrontWindsor Waterfront Park
Windsor Waterfront Park
Arunita Jaekel, Ph.D.Dr. Arunita Jaekel
Dr. Arunita Jaekel
Jessica Chen, Ph.D.Dr. Jessica Chen
Dr. Jessica Chen
Dr. Luis RuedaDr. Luis Rueda
Dr. Luis Rueda
Dr. Robert KentDr. Robert Kent
Dr. Robert Kent
Christie Ezeife, Ph.D.Dr. Christie Ezeife
Dr. Christie Ezeife
Xiaobu Yuan, Ph.D.Dr. Xiaobu Yuan
Dr. Xiaobu Yuan
Robin Gras, Ph.D.Dr. Robin Gras
Dr. Robin Gras
Imran Ahmad, Ph.D.Dr. Imran Ahmad
Dr. Imran Ahmad
Dr. Ziad Kobti lecturingDr. Ziad Kobti
Dr. Ziad Kobti
Dr. Scott GoodwinDr. Scott Goodwin
Dr. Scott Goodwin

Exact and Approximation Algorithms for Some Problems with Applicaitons

Add this event into your calendar using the iCAL format
  • Mon, 12/11/2017 - 2:00pm - 4:00pm

Exact and Approximation Algorithms for Some Problems with Applications

PhD. Comprehensive Exam by:

Md Zamilur Rahman

Date: Monday, December 11, 2017
Time: 2:00pm-4:00pm
Location: LT-3115

Domination problem has been extensively researched and has many applications in several areas including operations research, computer networks, document summarization, social networking, etc. The dominating set (DS) is a subset of vertices such that each vertex in the dominating set or has a neighbor in the dominating set. A connected dominating set (CDS) is a connected DS. Due to different requirements in a problem, people have studied many different variations of the domination problem including k-tuple dominating set, k-total dominating set, k-dominating set, m-fold CDS, alpha domination, and so on. We discuss different domination problems with applications.

We also discuss the point placement problem in the plane, which is a special case of the graph embedding problem of Saxe: For a given incomplete edge-weighted graph G and a parameter k, the problem is to map the vertices of G to points in an Euclidean k-space such that any two vertices of G, connected by an edge are mapped to points, whose distance is equal to the weight of the edge and deciding if such an embedding exists is strongly NP-hard. For a given set of points a distance query graph is generated and submitted to the adversary where adversary is the source of true distances. The motivation of this study is closely related to sensor network localization problem. This will leave many openings to explore and both will fall under graph algorithms.

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

See More: