講演抄録/キーワード |
講演名 |
2013-10-18 11:15
距離遺伝グラフにおけるハミルトン閉路問題 ○神保孝則・平田富夫(名大) COMP2013-33 |
抄録 |
(和) |
無向グラフ$G=(V,E)$に対し, $G$のすべての頂点を丁度1度ずつ通る閉路をハミルトン閉路と呼び, $G$にハミルトン閉路が存在するか否かを判定する問題をハミルトン閉路問題と呼ぶ.
この問題は一般的なグラフに対してNP完全である[3].
本研究ではグラフを距離遺伝グラフに制限することで多項式時間でハミルトン閉路問題を解くアルゴリズムを提案する.
距離遺伝グラフに対しては文献[1]で計算時間が$O(|V|^2)$のアルゴリズムが提案されているが, 本研究ではそれとは異なるアプローチのアルゴリズムを提案する. |
(英) |
(Not available yet) |
キーワード |
(和) |
ハミルトン閉路 / 距離遺伝グラフ / / / / / / |
(英) |
Hamiltonian cycle / Distance hereditary graph / / / / / / |
文献情報 |
信学技報, vol. 113, no. 252, COMP2013-33, pp. 9-12, 2013年10月. |
資料番号 |
COMP2013-33 |
発行日 |
2013-10-11 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-33 |