E-viri
Recenzirano
Odprti dostop
-
Asahiro, Yuichi; Eto, Hiroshi; Hanaka, Tesshu; Lin, Guohui; Miyano, Eiji; Terabaru, Ippei
Theoretical computer science, 10/2023, Letnik: 975Journal Article
For a graph G=(V,E) and a subset S⊆V of vertices, a vertex is happy if all its neighbor vertices in G are contained in S. Given a connected undirected graph and an integer k, the Maximum Happy Set Problem (MaxHS) asks to find a set S of k vertices which maximizes the number of happy vertices in S (note that all happy vertices in V belong to S). We proposed an algorithm for MaxHS on proper interval graphs in Theor. Comput. Sci. 866 (2021) 123–144. However, due to a wrong observation made by the authors, it works only on proper interval graphs obeying the observation. In this corrigendum, we propose a new algorithm which runs in O(k|V|logk+|E|) time for proper interval graphs.
