文献

J-GLOBAL ID：201702237448954334   整理番号：17A1548369

kクリークの動的記述的複雑性【Powered by NICT】

The dynamic descriptive complexity of k-clique

著者 (1件)： Zeume Thomas (TU Dortmund University, Germany)
資料名： Information and Computation  (Information and Computation)
巻： 256  ページ： 9-22  発行年： 2017年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本研究ではk-clique質問の動的記述の複雑さを研究した。端は挿入される可能性がある場合,k-cliqueは引数 1の量化記号無し更新プログラムによって保持されることが示されるが,引数K, 2(単項補助関数の存在下でも)の量化記号無し更新プログラムによって維持できない。これは挿入のもとでの量化記号無し更新プログラムのためのグラフ質問のためのアリティ階層を確立した。下界の証明Ramsey数のための上界と下界を用いた。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： グラフ ,  *量化記号
準シソーラス用語： 上界 ,  下界 ,  *複雑性 , 【Automatic Indexing@JST】

著者キーワード (3件)： 動的複雑性 ,  k-クリーク ,  Ramsey数

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (3件)： クリーク ,  記述 ,  複雑性