Geodesic
The Minimum Consistent Spanning Subset Problem on Trees
Ahmad Biniaz1 ; Parham Khamsepour1
1 School of Computer Science, University of Windsor
Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 81-93.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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\notin S$ has the same color as its nearest neighbor in $S$. This problem is NP-complete. A recent result of Dey, Maheshwari, and Nandy (2021) gives a polynomial-time algorithm for the MCS problem on two-colored trees. A block is a maximal connected set of vertices of the same color. We introduce a variant of the MCS problem, namely the minimum consistent spanning subset problem, for which we require the set $S$ to contain a vertex from every block of the graph such that every vertex $v\notin S$ has a nearest neighbor in $S$ that is in the same block as $v$. We observe that this problem is NP-hard on general graphs. We present a polynomial-time algorithm for this problem on trees.
DOI : 10.7155/jgaa.v28i1.2929
Keywords: minimum consistent subset, minimum consistent spanning subset, nearest neighbor, dynamic programming

Ahmad Biniaz 1 ; Parham Khamsepour 1

1 School of Computer Science, University of Windsor 
@article{JGAA_2024_28_1_a3,
     author = {Ahmad Biniaz and Parham Khamsepour},
     title = {The {Minimum} {Consistent} {Spanning} {Subset} {Problem} on {Trees}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {81--93},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2024},
     doi = {10.7155/jgaa.v28i1.2929},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2929/}
}
TY  - JOUR
AU  - Ahmad Biniaz
AU  - Parham Khamsepour
TI  - The Minimum Consistent Spanning Subset Problem on Trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 81
EP  - 93
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2929/
DO  - 10.7155/jgaa.v28i1.2929
LA  - en
ID  - JGAA_2024_28_1_a3
ER  - 
%0 Journal Article
%A Ahmad Biniaz
%A Parham Khamsepour
%T The Minimum Consistent Spanning Subset Problem on Trees
%J Journal of Graph Algorithms and Applications
%D 2024
%P 81-93
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2929/
%R 10.7155/jgaa.v28i1.2929
%G en
%F JGAA_2024_28_1_a3
Ahmad Biniaz; Parham Khamsepour. The Minimum Consistent Spanning Subset Problem on Trees. Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 81-93. doi : 10.7155/jgaa.v28i1.2929. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2929/

Cité par Sources :