| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-08-10 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Complexity and approximability of the happy set problem |
|
言語 |
en |
| その他のタイトル |
|
|
その他のタイトル |
Complexity and Approximability of the Happy Set Problem |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Asahiro, Yuichi
Eto, Hiroshi
Hanaka, Tesshu
Lin, Guohui
宮野, 英次
Terabaru, Ippei
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
In this paper we study the approximability of the MAXIMUM HAPPY SET problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2Δ+1)-approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard. |
| 書誌情報 |
en : Theoretical Computer Science
巻 866,
p. 123-144,
発行日 2021-04-08
|
| 出版社 |
|
|
出版者 |
Elsevier |
| DOI |
|
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1016/j.tcs.2021.03.023 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
03043975 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1879-2294 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2021 Elsevier B.V. All rights reserved. |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Maximum happy set problem |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Approximability |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Computational complexity |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Bipartite graphs |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Cubic graphs |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Block graphs |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Interval graphs |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
10363366.pdf (411 KB)
