| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-09-12 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Parameterized algorithms for the Happy Set problem |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Asahiro, Yuichi
Eto, Hiroshi
Hanaka, Tesshu
Lin, Guohui
宮野, 英次
Terabaru, Ippei
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
In this paper we study the parameterized complexity for the Maximum Happy Set problem (MaxHS): 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. In this paper we first show that MaxHS is W[1]-hard with respect to k even if the input graph is a split graph. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by tree-width, by clique-width plus k, by neighborhood diversity, or by cluster deletion number. |
|
言語 |
en |
| 書誌情報 |
en : Discrete Applied Mathematics
巻 304,
p. 32-44,
発行日 2021-07-24
|
| 出版社 |
|
|
出版者 |
Elsevier |
| DOI |
|
|
関連タイプ |
isVersionOf |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1016/j.dam.2021.07.005 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0166-218X |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1872-6771 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2021 Elsevier B.V. All rights reserved. |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
Maximum happy set problem |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
parameterized complexity |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
fixed-parameter tractability |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
graph parameters |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
10376843.pdf (1.2 MB)
