December 7, 2022    
1:00 pm - 2:00 pm


Bookings closed


Essex Hall Room 122
401 Sunset Avenue, Windsor, Ontario, N9B 3P4
Map Unavailable

The School of Computer Science is pleased to present…


Minimum Consistent Spanning Subset for Multi-Colored Trees 



MSc Thesis Proposal by: Parham Khamsepour 


Date: Wednesday, December 7, 2022 

Time: 1:00 pm-2:00 pm 

Location: Essex Hall, Room 122 



Given a set P of coloured points in the plane, the Minimum Consistent Subset (MCS) problem asks for a subset S of P such that every point of P is closest to a point with the same colour in S. This problem is widely used in areas involving nearest neighbours such as speech and handwriting recognition. This problem is NP-hard even for two-coloured point sets. The MCS problem can also be defined on graphs where the distance between two vertices is the length of the shortest path between them. We study a variant of the MCS problem on trees. This variant is called the Minimum Consistent Spanning Subset problem and has an extra constraint that the subset must span all the blocks in the tree, where a block is a maximal connected subtree of vertices of the same colour. We propose an algorithm that can correctly compute the Minimum Consistent Spanning Subset for a given multi-coloured tree using a bottom-up dynamic programming approach.


Keywords: Minimum Consistent Subset, Nearest neighbour, graph theory, dynamic programming


MSc Thesis Committee:  

Internal Reader: Dr. Dan Wu

External Reader: Dr. Mehdi Sangani Monfared

Advisor: Dr. Ahmad Biniaz


This event is fully booked.

No Responses

Leave a Reply

Your email address will not be published. Required fields are marked *