WEKO3
アイテム
Graph Classes and Approximability of the Happy Set Problem
http://hdl.handle.net/10228/0002000014
http://hdl.handle.net/10228/000200001483a5794e-39ed-4a71-91db-16ff9b2ef3a4
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
978-3-030-58150-3_27.pdf (391 KB)
|
|
| Item type | 学術雑誌論文 = 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
× Asahiro, Yuichi
× Eto, Hiroshi
× Hanaka, Tesshu
× Lin, Guohui
× 宮野, 英次
WEKO
6037
× 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. | |||||||||||||||||||||||
| 書誌情報 |
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 | |||||||||||||||||||||||
| 著作権関連情報 | ||||||||||||||||||||||||
| 権利情報 | 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 | |||||||||||||||||||||||
