お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年10月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2017-12-21 11:50
部分グラフクラス上での最大k-パス頂点被覆問題
八木田 剛宮野英次斎藤寿樹九工大)・上原隆平北陸先端大)・Tom C. van der Zandenユトレヒト大ISEC2017-76 COMP2017-30
抄録 (和) 本論文では,$k$-パス頂点被覆問題の最大化問題,最大$k$-パス頂点被覆問題(textsf{Max$P_k$VC}問題)を新たに導入する.$k$頂点による道(パス),すなわち距離が$k-1$となるような道は$k$-パスと呼ばれる.もし$k$-パス$P_k$上に,頂点集合$S$中の点$v$が含まれているならば,集合$S$もしくは頂点$v$が$P_k$を被覆するという.グラフ$G=(V,E)$と整数$s$が与えられたとき,textsf{Max$P_k$VC}問題は,被覆された$k$-パスの本数が最大となるような$s$個の頂点による頂点部分集合$Ssubseteq V$を見つけることを目的とする問題である.textsf{Max$P_k$VC}問題は一般的にNP-困難な問題である.本論文では入力グラフを部分グラフに限定したときのtextsf{Max$P_k$VC}問題の計算困難性/容易性を考える.本論文ではtextsf{Max$P_3$VC}問題とtextsf{Max$P_4$VC}問題がそれぞれスプリットグラフ,弦グラフを入力とした時でさえもNP-困難のままであることを示す.更に,入力グラフの木幅が定数に限定されているときに,textsf{Max$P_3$VC}問題を多項式時間で解くことのできるアルゴリズムも示す. 
(英) This paper introduces the maximum version of the $k$-path vertex cover problem, called the textsc{Maximum $k$-Path Vertex Cover} problem (textsf{Max$P_k$VC} 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 $P_k$ includes a vertex $v$ in a vertex set $S$, then we say that $S$ or $v$ covers $P_k$. Given a graph $G = (V, E)$ and an integer $s$, the goal of textsf{Max$P_k$VC} is to find a vertex subset $Ssubseteq V$ of at most $s$ vertices such that the number of $k$-paths covered by $S$ is maximized. textsf{Max$P_k$VC} is generally NP-hard. In this paper we consider the tractability/intractability of textsf{Max$P_k$VC} on subclasses of graphs: We prove that textsf{Max$P_3$VC} and textsf{Max$P_4$VC} 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 textsf{Max$P_3$VC} can be solved in polynomial time.
キーワード (和) 最大k-パス頂点被覆問題 / NP-困難性 / 多項式時間アルゴリズム / スプリットグラフ / 木グラフ / / /  
(英) Maximum k-Path Vertex Cover Problem / NP-hardness / polynomial time algorithm / split graphs / tree graphs / / /  
文献情報 信学技報, vol. 117, no. 370, COMP2017-30, pp. 25-31, 2017年12月.
資料番号 COMP2017-30 
発行日 2017-12-14 (ISEC, COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード ISEC2017-76 COMP2017-30

研究会情報
研究会 ISEC COMP  
開催期間 2017-12-21 - 2017-12-22 
開催地(和) 高知工科大学永国寺キャンパス 
開催地(英) Eikokuji Campus, Kochi University of Technology 
テーマ(和) 一般 
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2017-12-ISEC-COMP 
本文の言語 日本語 
タイトル(和) 部分グラフクラス上での最大k-パス頂点被覆問題 
サブタイトル(和)  
タイトル(英) Maximum k-path Vertex Cover Problem on Graph Classes 
サブタイトル(英)  
キーワード(1)(和/英) 最大k-パス頂点被覆問題 / Maximum k-Path Vertex Cover Problem  
キーワード(2)(和/英) NP-困難性 / NP-hardness  
キーワード(3)(和/英) 多項式時間アルゴリズム / polynomial time algorithm  
キーワード(4)(和/英) スプリットグラフ / split graphs  
キーワード(5)(和/英) 木グラフ / tree graphs  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 八木田 剛 / Tsuyoshi Yagita / ヤギタ ツヨシ
第1著者 所属(和/英) 九州工業大学 (略称: 九工大)
Kyushu Institute of Technology (略称: Kyutech)
第2著者 氏名(和/英/ヨミ) 宮野 英次 / Eiji Miyano / ミヤノ エイジ
第2著者 所属(和/英) 九州工業大学 (略称: 九工大)
Kyushu Institute of Technology (略称: Kyutech)
第3著者 氏名(和/英/ヨミ) 斎藤 寿樹 / Toshiki Saitoh / サイトウ トシキ
第3著者 所属(和/英) 九州工業大学 (略称: 九工大)
Kyushu Institute of Technology (略称: Kyutech)
第4著者 氏名(和/英/ヨミ) 上原 隆平 / Ryuhei Uehara / ウエハラ リュウヘイ
第4著者 所属(和/英) 北陸先端科学技術大学院大学 (略称: 北陸先端大)
Japan Advanced Institute of Science and Technology (略称: JAIST)
第5著者 氏名(和/英/ヨミ) Tom C. van der Zanden / Tom C. van der Zanden / Tom C. van der Zanden
第5著者 所属(和/英) ユトレヒト大学 (略称: ユトレヒト大)
Utrecht University (略称: Utrecht U.)
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2017-12-21 11:50:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-ISEC2017-76,IEICE-COMP2017-30 
巻番号(vol) IEICE-117 
号番号(no) no.369(ISEC), no.370(COMP) 
ページ範囲 pp.25-31 
ページ数 IEICE-7 
発行日 IEICE-ISEC-2017-12-14,IEICE-COMP-2017-12-14 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会