文献

J-GLOBAL ID：201902255004311531   整理番号：19A1043130

非関連頂点を持つグラフの木幅に関する下界【JST・京大機械翻訳】

A lower bound on the tree-width of graphs with irrelevant vertices

著者 (2件)： Adler Isolde (School of Computing, University of Leeds, United Kingdom of Great Britain and Northern Ireland) ,  Krause Philipp Klaus (Albert-Ludwigs-Universitaet Freiburg, Germany)
資料名： Journal of Combinatorial Theory. Series B  (Journal of Combinatorial Theory. Series B)
巻： 137  ページ： 126-136  発行年： 2019年 
JST資料番号： E0780A  ISSN： 0095-8956  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 非結合経路問題に対するそれらの有名なアルゴリズムに対して,RobertsonとSeymourは,グラフGの木幅が少なくともf(k)であるならば,Gが解に無関係な頂点(RobertsonとSeymour(2012))を含むような関数fが存在することを証明した。f上に単一指数関数的下限を与えた。この限界は平面グラフに対しても成立する。Copyright 2019 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 平面グラフ ,  *グラフ ,  指数関数 ,  アルゴリズム
準シソーラス用語： *下界 ,  *木幅 , 【Automatic Indexing@JST】

著者キーワード (6件)： 互いに素なパス問題 ,  非関連頂点 ,  重要な連鎖 ,  ユニークな結合 ,  平面グラフ ,  木幅

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

タイトルに関連する用語 (4件)： 頂点 ,  グラフ ,  木幅 ,  下界