抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
グラフG=(V,E)および各頂点v→Vに対して,集合{0,1.,d_G(v)}の部分集合B(v)は,GのBマッチングは,各頂点vに対してd_F(v)|ΔB(v)のような任意の集合F⊆Eである。一般的マッチング問題は,与えられたグラフにおけるBマッチングの存在を問う。集合B(v)は,k+1,k+p otin B(v)およびk+p+1{B(v)のような多数のk∈B(v)が存在するならば,長さpのemギャップを持つと言われている。任意の制約なしに,一般的マッチング問題はNP完全である。しかし,もしセットB(v)が1より大きい長さのギャップを含むならば,この問題を多項式時間で解決することができ,そして,それが存在するならば,Bマッチングを見つけるためのアルゴリズムを示す。本論文では,エッジの最大(または最小)数を持つBマッチングの発見に興味を持つ一般的マッチング問題のバージョンを考察した。セットB(v)が1より大きい長さのギャップを含む場合について,最大重みBマッチングに対する最初の多項式時間アルゴリズムを示した。【JST・京大機械翻訳】
