有向グラフにおけるk枝連結性の検査

概要

論文の詳細を見る
本報告では、次数に上限のある有向グラフがk枝連結であるか、またはた枝連結から⋴遠隔であるかを検査する、グラフの頂点と枝の数によらない定数時間アルゴリズムを示す。頂点数n、次数の上限dの有向グラフGがk枝連結から⋴遠隔であるとは、次数の上限を保ったままGをk枝連結にするのに、少なくとも⋴dn本の辺の追加及び削除が必要であることを言う。本報告で示す検査アルゴリズムは、性質検査(Property Testing)と呼ばれる概念に基づいている。これは入力グラフがk枝連結であれば2/3以上の確率で受理し、k枝連結から⋴遠隔であれば2/3以上の確率で拒否するものとして定義される。どちらでもないグラフに対しては、何を出力してもかまわない。我々は、k-1枝連結なグラフに対してO(d(c/(⋴d))^k log 1/(⋴d))(c>1は定数)時間、一般のグラフに対してO(d((ck)/(⋴d))^k log k/(⋴d))(⋴>1は定数)時間の検査アルゴリズムを得た。
社団法人電子情報通信学会の論文
2007-06-22