| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-07-31 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Graph Classes 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) (2Δ+1)-approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the input is a connected graph and its maximum degree Δ is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to proper interval graphs, or block graphs. We prove nevertheless that MaxHS remains NP-hard even for bipartite graphs or for cubic graphs. |
| 書誌情報 |
en : Lecture Notes in Computer Science
巻 12273,
p. 335-346,
発行日 2020-08-27
|
| 出版社 |
|
|
出版者 |
Springer |
| DOI |
|
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1007/978-3-030-58150-3_27 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-030-58149-7 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-030-58150-3 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0302-9743 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1611-3349 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2020 Springer Nature Switzerland AG. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-58150-3_27. |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
978-3-030-58150-3_27.pdf (391 KB)
