6K-04
グラフに含まれる大きな内周を持つ部分グラフの効率良い列挙
○栗田和宏（北大），Alessio Conte（Università di Pisa），和佐州洋，宇野毅明（NII），有村博紀（北大）
内周はグラフに含まれる最小の閉路長を表し,
グラフの内周を計算する問題はよく研究されている.
ItaiとRodehは一般グラフの内周を計算する
非自明な最初のアルゴリズムを開発した.
このアルゴリズムは最悪時O(nm)時間で動作し,
平均時間O(n^2)時間で動作する.
重みなし平面グラフに対しては,
DjidjevがO(n^{5/4} log n)時間アルゴリズムを与え,
Changらがこのアルゴリズムを改良し線形時間アルゴリズムを与えた.
我々の知る限りでは
大きな内周を持つ連結な部分グラフを列挙する
アルゴリズムは存在しない.
本論文では,これらの問題を解く列挙アルゴリズムを与える.
このアルゴリズムの単純な拡張により,k以上の内周を持つ
重み付きグラフの部分グラフや非連結なグラフの列挙も可能である.
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会