Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144, (S0304397521001699), (10.1016/j.tcs.2021.03.023)]

Yuichi Asahiro; Hiroshi Eto; Tesshu Hanaka; Guohui Lin; Eiji Miyano; Ippei Terabaru

doi:10.1016/j.tcs.2023.114114

Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144, (S0304397521001699), (10.1016/j.tcs.2021.03.023)]

Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, Ippei Terabaru

Mathematical Informatics

Research output: Contribution to journal › Comment/debate › peer-review

Abstract

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|log⁡k+|E|) time for proper interval graphs.

Original language	English
Article number	114114
Journal	Theoretical Computer Science
Volume	975
DOIs	https://doi.org/10.1016/j.tcs.2023.114114
Publication status	Published - Oct 9 2023

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2023.114114

Cite this

@article{4d43b0a1e587485d8bc65d77d572a073,

title = "Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144, (S0304397521001699), (10.1016/j.tcs.2021.03.023)]",

abstract = "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|log⁡k+|E|) time for proper interval graphs.",

author = "Yuichi Asahiro and Hiroshi Eto and Tesshu Hanaka and Guohui Lin and Eiji Miyano and Ippei Terabaru",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier B.V.",

year = "2023",

month = oct,

day = "9",

doi = "10.1016/j.tcs.2023.114114",

language = "English",

volume = "975",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144, (S0304397521001699), (10.1016/j.tcs.2021.03.023)]

AU - Asahiro, Yuichi

AU - Eto, Hiroshi

AU - Hanaka, Tesshu

AU - Lin, Guohui

AU - Miyano, Eiji

AU - Terabaru, Ippei

PY - 2023/10/9

Y1 - 2023/10/9

N2 - 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|log⁡k+|E|) time for proper interval graphs.

AB - 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|log⁡k+|E|) time for proper interval graphs.

UR - http://www.scopus.com/inward/record.url?scp=85169340144&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85169340144&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2023.114114

DO - 10.1016/j.tcs.2023.114114

M3 - Comment/debate

AN - SCOPUS:85169340144

SN - 0304-3975

VL - 975

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 114114

ER -

Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144, (S0304397521001699), (10.1016/j.tcs.2021.03.023)]

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this