文献

J-GLOBAL ID：201702233653474156   整理番号：17A1185891

失敗した0フォーシングの計算量について【Powered by NICT】

On the complexity of failed zero forcing

著者 (1件)： Shitov Yaroslav (National Research University Higher School of Economics, 20 Myasnitskaya Ulitsa, Moscow 101000, Russia)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 660  ページ： 102-104  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Gは,その頂点が二つのサブセットに分割する単純グラフ,「充填」頂点と呼ばれ,「空の」頂点とする。vがuのユニークな空近傍であれば,頂点vは充填した頂点uによって強制されたと言われている,繰り返し強制を充填することによりGのすべての頂点を埋めることができる,充填した頂点強制集合の初期集合と呼ぶ。グラフのいわゆる失敗した強制数,強制されないセットの最大濃度を検討した。Ansill,Jacob,Penzellna,Saavedraの最近の疑問に答えることは,この量を計算するためにNP困難であることを証明した。証明もスキュー失敗した強制数と呼ばれる関連グラフ不変量。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： グラフ ,  *計算量 ,  NP困難 ,  部分集合 ,  ゆがみ ,  不変量
準シソーラス用語： 単純グラフ , 【Automatic Indexing@JST】

著者キーワード (2件)： グラフ理論 ,  0フォーシング

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

タイトルに関連する用語 (2件)： 失敗 ,  計算量