文献

J-GLOBAL ID：202002290566839378   整理番号：20A0425893

k経路頂点被覆の再構成【JST・京大機械翻訳】

Reconfiguring k-path Vertex Covers

著者 (3件)： Hoang Duc A. (Kyushu Institute of Technology, Fukuoka, Japan) ,  Suzuki Akira (Tohoku University, Sendai, Japan) ,  Yagita Tsuyoshi (Kyushu Institute of Technology, Fukuoka, Japan)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12049  ページ： 133-145  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： グラフGの頂点部分集合Iは,Gにおけるk頂点上のあらゆる経路がIから少なくとも1つの頂点を含むならば,k経路頂点カバーと呼ばれる。k-経路頂点被覆(k-PVCR)問題は,1つのk経路頂点カバーを,各中間メンバーが与えられた再構成ルールを正確に適用することにより,その先行者から得られるk経路頂点カバーのシーケンスを介してもう一つに変換することができる。既知の再構成ルール([数式:原文を参照],[数式:原文を参照],[数式:原文を参照])下のグラフクラスの観点からk-PVCRの計算複雑性を調べた。Vertex Cover Reconfiguration(VCR)問題として知られている[数式:原文を参照]に対する問題は,文献において良く研究されている。平面グラフ,有界帯域幅グラフ,コードグラフ,および二部グラフを含む異なるグラフクラス上のVCRに対する既知の硬さ結果がk-PVCRに対して拡張できることを示した。特に,一般グラフ上のk-PVCRに対する複雑さの分割を証明した。最大次数が3(および平面)である場合には,問題は[数式:原文を参照]完全であるが,最大次数が2(すなわち経路とサイクル)である場合には,問題は多項式時間で解くことができる。さらに,各[数式:原文を参照]と[数式:原文を参照]の下でツリー上のk-PVCRに対する多項式時間アルゴリズムも設計した。さらに,経路,サイクル,およびツリーに関して,著者らは,1つが,2つの与えられたk経路頂点カバーの間の再構成シーケンスをどのように構築できるかについて述べた。特に,経路上では,構築された再構成シーケンスは最短である。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 平面グラフ ,  硬度 ,  完全性 ,  再構成 ,  *計算量 ,  帯域幅 ,  部分集合
準シソーラス用語： 多項式時間アルゴリズム ,  多項式時間 ,  二部グラフ ,  有界 ,  *頂点被覆 , 【Automatic Indexing@JST】

著者キーワード (5件)： 組合せ再構成 ,  計算の複雑さ ,  Kパス頂点被覆 ,  [数式:原文を参照]-完全性 ,  多項式時間アルゴリズム

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (3件)： 経路 ,  頂点被覆 ,  再構成