文献

J-GLOBAL ID：202002210552202489   整理番号：20A1003917

小被覆パラメータに対するスパース障害【JST・京大機械翻訳】

Sparse obstructions for minor-covering parameters

著者 (4件)： Chatzidimitriou Dimitris (Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece) ,  Thilikos Dimitrios M. (AlGCo project-team, LIRMM, Universite de Montpellier, CNRS, Montpellier, France) ,  Thilikos Dimitrios M. (Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece) ,  Zoros Dimitris (Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 278  ページ： 28-50  発行年： 2020年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフHと非負整数kの有限集合を与えて,著者らは,その除去がHにおけるグラフを小さくすることなくグラフを提供するk頂点を持つあらゆるグラフGを含む集合としてAk(H)を定義した。Hが少なくとも1つの平面グラフを含むならば,Ak(H)における各閉塞は,Hの選択のみに依存して,いくつかのcHに対して,ほとんどのKCH頂点を持つことが知られている。本論文では,あるクラスのスパースグラフに属するAk(H)におけるグラフのサイズを調べた。特に,すべてのグラフFに対して,Hが少なくとも1つの平面グラフと連結グラフを含む場合,Fトポロジー的な少数のAk(H)のすべてのグラフは,cF,HがHとFの選択に排他的に依存する,ほとんどのcF,H・k頂点を持つことを証明した。著者らの結果は,グラフパラメータに関する2つのより一般的な条件,すなわち,有限整数指数特性と射影分解性の結果であり,それは,障害のための線形限界を証明するための一般的なフレームワークとして役立つことができる。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 位相幾何学 ,  *被覆 ,  平面グラフ ,  線形性 ,  射影
準シソーラス用語： 連結グラフ , 【Automatic Indexing@JST】

著者キーワード (6件)： 閉塞集合 ,  グラフマイナ ,  頂点拡張 ,  突起分解 ,  木の分解 ,  有限整数指数

分類 (2件)： 集合論  (AB10000I) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (2件)： パラメータ ,  障害