グラフに含まれる大きな内周を持つ部分グラフの効率良い列挙

• 栗田, 和宏

• Alessio, Conte

• 和佐, 州洋

• 宇野, 毅明

• 有村, 博紀

抄録

内周はグラフに含まれる最小の閉路長を表し,グラフの内周を計算する問題はよく研究されている.ItaiとRodehは一般グラフの内周を計算する非自明な最初のアルゴリズムを開発した.このアルゴリズムは最悪時O(nm)時間で動作し,平均時間O(n^2)時間で動作する.重みなし平面グラフに対しては,DjidjevがO(n^{5/4} log n)時間アルゴリズムを与え,Changらがこのアルゴリズムを改良し線形時間アルゴリズムを与えた.我々の知る限りでは大きな内周を持つ連結な部分グラフを列挙するアルゴリズムは存在しない.本論文では,これらの問題を解く列挙アルゴリズムを与える.このアルゴリズムの単純な拡張により,k以上の内周を持つ重み付きグラフの部分グラフや非連結なグラフの列挙も可能である.

収録刊行物

• 第80回全国大会講演論文集

  第80回全国大会講演論文集 2018 (1), 347-348, 2018-03-13

キーワード

• ソフトウェア科学・工学

詳細情報

• CRID: 1050011097170031360
• NII論文ID: 170000176712
• NII書誌ID: AN00349328
• Web Site: http://id.nii.ac.jp/1001/00187613/
• 本文言語コード: ja
• 資料種別: conference paper
• データソース種別:
  • IRDB
  • CiNii Articles