文献

J-GLOBAL ID：201702231873630607   整理番号：17A1185930

最小5と木における円周の連結グラフにおける次数比例しきい値のための動的独占【Powered by NICT】

Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees

著者 (2件)： Gentner Michael (Institute of Optimization and Operations Research, Ulm University, Ulm, Germany) ,  Rautenbach Dieter (Institute of Optimization and Operations Research, Ulm University, Ulm, Germany)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 667  ページ： 93-100  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Gをグラフとし,ρ∈[0 1]をさせた。Gの頂点の集合Dでは,それらは[ρdG(u)]近傍を少なくともた場合セットHρ(D)はDから出発して,電流セットにuさらに頂点を添加反復により発生させた。Hρ(D)がGのすべての頂点を含むならば,Dは不可逆動的独占またはしきい値関数U→[ρdG(u)]と関連した完全な目標集合として知られている。hρ(G)は,このような不可逆動的独占の最小濃度とする。少なくとも1ρ最大次数の連結グラフGに対して,Changはρ(G)≦5.83ρn(G),ChangとLyuuによるHρ(G)≦4.92ρn(G)に改良されたを示した。ε>0では,ある程度のρ(ε)∈(0 , 1)である(0,ρ(ε))におけるρ毎に時間ρ(G)≦(2 + ε)ρn(G)ことを示し,各は少なくとも1ρ,少なくとも5周最大次数を持つグラフGを接続した。,(0+1+]におけるρ毎と少なくとも1ρ指標を持つところ毎木T時間ρ(T)≦ρn(T)ことを示した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 電流 ,  *グラフ ,  最小濃度
準シソーラス用語： *次数 ,  *連結グラフ , 【Automatic Indexing@JST】

著者キーワード (2件)： 不可逆動的独占 ,  完全ターゲットセット

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

タイトルに関連する用語 (6件)： 木 ,  連結グラフ ,  次数 ,  比例 ,  しきい値 ,  独占