2-連結グラフの2分割アルゴリズム

概要

論文の詳細を見る
本報告では,グラフ2分割問題を解く効率の良いアルゴリズムを与える.G=(V,E)は点集合V,辺集合Eを持つ無向単純グラフとする.点集合V'CVによって誘導されるGの部分グラフをG[V']と書く.Gの2つの点x,y∈V及びn_x+n_y=|V|なる2つの正の整数n_xとn_yが与えられたときに,集合Vの2分割V_x,V_y(=V-V_x)でX∈V_x,y∈V_y,|V_x|=n_x,|V_y|=n_yかつ、G[V_x]及びG[V_y]が連結であるようなものを見つけたい.この2分割間題はGを二部グラフに,n_x=n_y=|V|/2であると限定してもNP完全であり[DF],一般のグラフに対する効率の良いアルゴリズムはありそうにない.本報告では,Gが2-連結である場合にこの問題をo(|V||E|)時間で解くアルゴリズムを与える.尚,E.Gyori[G]は2-連結グラフGには上のような2分割が必ず存在することを証明しているが、本文のアルゴリズムはその証明とは全く異なる.
一般社団法人情報処理学会の論文
1988-09-12