| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-07-31 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Complexity of the Maximum k-Path Vertex Cover Problem |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
宮野, 英次
斎藤, 寿樹
Uehara, Ryuhei
Yagita, Tsuyoshi
van der Zanden, Tom C.
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
This paper introduces the maximum version of the k-path vertex cover problem, called the MAXIMUM k-PATH VERTEX COVER problem (MaxPkVC for short): A path consisting of k vertices, i.e., a path of length k−1 is called a k-path. If a k-path Pk includes a vertex v in a vertex set S, then we say that S or v covers Pk. Given a graph G=(V,E) and an integer s, the goal of MaxPkVC is to find a vertex subset S⊆V of at most s vertices such that the number of k-paths covered by S is maximized. MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs: We prove that MaxP3VC and MaxP4VC remain NP-hard even for split graphs and for chordal graphs, respectively. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time. |
|
言語 |
en |
| 備考 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
12th International Conference and Workshops on Algorithms and Computation, WALCOM 2018, March 3-5, 2018, Dhaka, Bangladesh |
|
言語 |
en |
| 書誌情報 |
en : Lecture Notes in Computer Science
巻 10755,
p. 240-251,
発行日 2018-01-31
|
| 出版社 |
|
|
出版者 |
Springer |
| DOI |
|
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1007/978-3-319-75172-6_21 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-319-75171-9 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-319-75172-6 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1611-3349 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0302-9743 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2018 Springer International Publishing AG, part of Springer Nature. 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-319-75172-6_21. |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
978-3-319-75172-6_21.pdf (201 KB)
