Wednesday, December 7, 2022 - 13:00 to 14:00
SCHOOL OF COMPUTER SCIENCE
The School of Computer Science is pleased to present…
MSc Thesis Proposal by: Parham Khamsepour
Date: Wednesday December 7, 2022
Time: 1:00pm-2:00pm
Location: Essex Hall, Room 122
Abstract:
Given a set P of colored 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 color in S. This problem is widely used in areas involving nearest neighbors such as speech and handwriting recognition. This problem is NP-hard even for two-colored 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 color. We propose an algorithm that can correctly compute the Minimum Consistent Spanning Subset for a given multi-colored tree using a bottom-up dynamic programming approach.
Keywords: Minimum Consistent Subset, Nearest neighbor, graph theory, dynamic programming
MSc Thesis Committee:
Internal Reader: Dr. Dan Wu
External Reader: Dr. Mehdi Sangani Monfared
Advisor: Dr. Ahmad Biniaz
MSc Thesis Proposal Announcement
5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716 csgradinfo@uwindsor.ca