講演抄録/キーワード |
講演名 |
2022-12-06 09:55
点素最短パス遷移の計算複雑性 ○斉藤 凜(東北大)・江藤 宏(九工大)・伊藤健洋(東北大)・上原隆平(北陸先端大) COMP2022-22 |
抄録 |
(和) |
本稿では,次のように定義される点素最短パス遷移問題について研究を行う.重みなしグラフにおいて端子対を繋ぐ点素最短パスの集合が2つ与えられたとき,それらを互いに遷移させられるか判定したい.ただし,1回に交換できる点は,集合に含まれる一つの最短パスの一点のみであり,その交換もまた点素最短パスの集合を生み出さなければならない.この点素最短パス遷移問題は,これまで研究されてきた最短パス遷移問題の一般化となっている.加えて本稿では,点素最短パスの最短遷移問題,すなわち点の交換回数を最小化する問題にも取り組む.本稿では,これらの問題の計算複雑性をグラフクラスの観点から解析し,いくつかの興味深い対比を与える. |
(英) |
|
キーワード |
(和) |
組合せ遷移 / グラフアルゴリズム / 点素パス / / / / / |
(英) |
/ / / / / / / |
文献情報 |
信学技報, vol. 122, no. 294, COMP2022-22, pp. 9-13, 2022年12月. |
資料番号 |
COMP2022-22 |
発行日 |
2022-11-29 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2022-22 |