ハイパーグラフの重み付き横断

摘要

我々は,有限ハイパグラフの横断の一般化である重み付き横断を考察する.入力ハイパーグラフAの各枝に割り当てられた非負の重みベクトルと非負の閥ベクトルが与えられたとき,重み付き横断を交わりをもたないAの枝の重み和が******ベクトル以下である極小な点集合と定義する．この重み付き横断は,部分横断,多重横断の一般化である.本論文では,すべての重み付き横断から成るハイパーグラフが双対制限されている,すなわち,その横断ハイパーグラフのサイズが,重み付き横断数と入力のハイパーグラフのサイズの多項式であることを示す.また,すべてのすべての重み付き横断を列挙する問題を別のハイパーグラフのすべての横断を列挙する問題,すなわち,有名なハイパーグラフ双対化問題に多項式時間で帰着できることを示す.系として,すべての重み付き横断の列挙が逐次擬多項式時間で可能であることも示す.