| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2024-04-25 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Independent Set Under a Change Constraint from an Initial Solution |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Asahiro, Yuichi
江藤, 宏
Korenaga, Kana
Lin, Guohui
宮野, 英次
Nonoue, Reo
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
In this paper, we study a type of incremental optimization variant of the MAXIMUM INDEPENDENT SET problem (MaxIS), called BOUNDED-DELETION MAXIMUM INDEPENDENT SET problem (BD-MaxIS): Given an unweighted graph G=(V,E), an initial feasible solution (i.e., an independent set) S0⊆V, and a non-negative integer k, the objective of BD-MaxIS is to find an independent set S⊆V such that |S0＼S≤k and |S| is maximized. The original MaxIS is generally NP-hard, but, it can be solved in polynomial time for perfect graphs (and therefore, comparability, co-comparability, bipartite, chordal, and interval graphs). In this paper, we show that BD-MaxIS is NP-hard even if the input is restricted to bipartite graphs, and hence to comparability graphs. On the other hand, fortunately, BD-MaxIS on co-comparability, interval, convex bipartite, and chordal graphs can be solved in polynomial time. Finally, we study the computational complexity on very similar variants of the MINIMUM VERTEX COVER and the MAXIMUM CLIQUE problems for graph subclasses. |
|
言語 |
en |
| 備考 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
International Conference on Algorithms and Complexity, CIAC 2023, 13-16 June,2023, Larnaca, Cyprus |
|
言語 |
en |
| 書誌情報 |
en : Lecture Notes in Computer Science
巻 13898,
p. 37-51,
発行日 2023-04-25
|
| 出版社 |
|
|
出版者 |
Springer |
| DOI |
|
|
関連タイプ |
isVersionOf |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1007/978-3-031-30448-4_4 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-031-30447-7 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-031-30448-4 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0302-9743 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1611-3349 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2023 The Author(s), under exclusive license to 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-031-30448-4_4. |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
| 論文ID（連携） |
|
|
値 |
10420553 |
| 連携ID |
|
|
値 |
11385 |
10420553.pdf (428 KB)
