文献

J-GLOBAL ID：201802219528717037   整理番号：18A0795784

次数に下界を持つスパンニング木【JST・京大機械翻訳】

Spanning tree with lower bound on the degrees

著者 (1件)： Kiraly Zoltan (Department of Computer Science and Egervary Research Group (MTA-ELTE), Eotvos University, Budapest Pazmany P. s. 1/C, H-1117, Hungary)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 242  ページ： 82-88  発行年： 2018年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 著者らは,いくつかの最近のEgawaとOzeki(2015,2014),およびHeら(2002)の結果に焦点を合わせた。また,より短い証明と多項式時間アルゴリズムを与えた。著者らは,最近,江川と小ze(2015)によって達成された程度に関する規定された下限を有するスパンニング木を有するための十分条件のための2つの新しい証明を提示した。最初のものは誘導を用いた自然証明であり,2番目のものはLovasz(1970)の定理への単純な縮小である。Frank(1975)のアルゴリズムを用いて,定理の条件を時間O(mn)においてチェックすることができ,さらに,条件が満たされている場合には,必要なスパンニング木も生成できることを示した。これはこの問題のための最初の多項式時間アルゴリズムを与える。次に,Weak Nine Dragon Tree Conjectureの最も単純な事例に対するこの定理の応用を示し,平面グラフのゲーム彩色数に対して,最初にHeら(2002)により発見された。最終的に,G[S]がコグラフであるときに,指定された程度の下限を持つスパンニング木を持つ良好な特性化のためのより短い証明と多項式時間アルゴリズムを与える。ここで,Sは少なくとも2つの程度の下限を持つ頂点の集合である。この定理は2014年の江川と小zeによって証明されたが,それらは多項式時間アルゴリズムを与えなかった。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ゲーム ,  平面グラフ ,  キャラクタリゼーション ,  *スパンニング木 ,  アルゴリズム ,  十分条件
準シソーラス用語： 彩色数 ,  多項式時間アルゴリズム ,  *下界 ,  *次数 , 【Automatic Indexing@JST】

著者キーワード (4件)： スパンニング木 ,  次数に対する規定下界 ,  ゲーム彩色数 ,  WNDT予想

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

タイトルに関連する用語 (3件)： 次数 ,  下界 ,  スパンニング木