MSc Thesis Defense Announcement of Parham Khamsepour:"The Minimum Consistent Spanning Subset Problem on Trees"

 

Date: Thursday April 20, 2023

Time:  10:00 am-12:00 pm

Location: Essex Hall, Room 122

 

Reminders: 1. Two-part attendance mandatory (sign-in sheet, QR Code) 2. Arrive 5-10 minutes prior to event starting - LATECOMERS WILL NOT BE ADMITTED. Note that due to demand, if the room has reached capacity, even if you are "early" admission is not guaranteed. 3. Please be respectful of the presenter by NOT knocking on the door for admittance once the door has been closed whether the presentation has begun or not (If the room is at capacity, overflow is not permitted (ie. sitting on floors) as this is a violation of the Fire Safety code). 4. Be respectful of the decision of the advisor/host of the event if you are not given admittance. The School of Computer Science has numerous events occurring soon.

 

 

Given a vertex-colored edge-weighted graph, the minimum consistent subset (MCS) problem asks for a minimum subset S of vertices such that every vertex v not in S has the same color as its nearest neighbor in S. This problem has applications in clustering and classification algorithms, specially in finding the optimal number of clusters in k-clustering algorithms. This problem is NP-complete. A recent result of Dey, Maheshwari, and Nandy (2021) gives a polynomial-time algorithm for the MCS problem on trees. In thesis we study the MCS problem on different settings, and discuss some of the shortcomings of the MCS problem for trees. We then introduce a variant of the MCS problem, namely the minimum consistent spanning subset (MCSS) problem, for which we require the set S to contain a vertex from every block of the graph, where a block is a maximal connected vertices of the same color. We observe that this problem is NP-hard on general graphs. We present an O(n4) time algorithm to find the MCSS on multi-colored weighted trees with n vertices. We also improve the running time for simple classes of trees.

 

Keywords: minimum consistent subset, minimum consistent spanning subset, nearest neighbor, dynamic programming

Internal Reader: Dr. Dan Wu
External Reader: Dr. Mehdi Sangani Monfared
Advisor:  Dr. Ahmad Biniaz
Chair: Dr. Yung (Peter) H. Tsin

 

 

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