文献

J-GLOBAL ID：201802228451151891   整理番号：18A1998684

有界長増大による木のマッチングの改善について【JST・京大機械翻訳】

On improving matchings in trees, via bounded-length augmentations

著者 (3件)： Bensmail Julien (Universite Cote d’Azur, CNRS, Inria, I3S, France) ,  Garnero Valentin (Universite Cote d’Azur, CNRS, Inria, I3S, France) ,  Nisse Nicolas (Universite Cote d’Azur, CNRS, Inria, I3S, France)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 250  ページ： 110-129  発行年： 2018年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Bergeの古典的な結果により,任意のグラフのマッチングは,その端がカバーされない交互経路を繰り返し増加させることにより,最大マッチングに変換できることが知られている。最近の研究において,NiSSe,SalchおよびWeberは,このプロセスに対して,ほとんどのkだけで長さを持つ経路の増大の影響を考慮している。グラフG,初期マッチングM ⊆E(G)および奇数整数kを与えると,問題は,Mから連続的に拡張できる大部分のkにおける長さの最大化経路を見出すことである。それらは,ほとんどのk=3における長さの経路だけを拡張することができるとき,そのような最も長いシーケンスを,任意のグラフに対して多項式時間で実行することができ,一方,任意のk≧5に対する同じ問題はNP困難であることを証明した。後者の結果は二部グラフに対して真のままであるが,木に対する同じ問題の複雑さの状態は知られていない。本研究は樹木に対するこの問題の複雑さに対して専用である。正側では,最初に,より多くのクラスの木に対して多項式時間で解くことができることを示した。すなわち,有界度木(動的計画法による),頂点および少なくとも3の程度のノードが十分に離れている木である。負の側において,長さの経路のみが拡張できる場合,最大次数3と任意の大きい格子を持つ平面二部グラフのクラスにおいて,k=3に対して問題は既にNP困難になることを示した。また,kが入力の一部であるとき,後者の問題は木においてNP困難であることを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 奇数 ,  動的計画法 ,  NP困難 ,  *マッチング ,  グラフ
準シソーラス用語： 次数 ,  複雑性 ,  二部グラフ ,  多項式時間 ,  最大マッチング ,  *有界 , 【Automatic Indexing@JST】

著者キーワード (3件)： 最大マッチング ,  有界長増大 ,  樹木

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： 有界 ,  木 ,  マッチング