Date of Award
6-1-2023
Publication Type
Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
dynamic programming;minimum consistent subset
Supervisor
Ahmad Biniaz
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Abstract
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 intro- duce 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(n^4)-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.
Recommended Citation
Khamsepour, Parham, "The Minimum Consistent Spanning Subset Problem on Trees" (2023). Electronic Theses and Dissertations. 9348.
https://scholar.uwindsor.ca/etd/9348