文献

J-GLOBAL ID：201802281724191255   整理番号：18A0276905

結合ネットワークにおける固定点とグラフ収縮における最大独立集合【Powered by NICT】

Fixed points in conjunctive networks and maximal independent sets in graph contractions

著者 (3件)： Aracena Julio (CI2MA and Departamento de Ingenieria Matematica, Universidad de Concepcion, Av. Esteban Iturra s/n, Casilla 160-C, Concepcion, Chile) ,  Richard Adrien (Laboratoire I3S, UMR CNRS 7271 & Universite de Nice-Sophia Antipolis, France) ,  Salinas Lilian (Department of Computer Sciences and CI2MA, University of Concepcion, Edmundo Larenas 215, Piso 3, Concepcion, Chile)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 88  ページ： 145-163  発行年： 2017年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフG,ループレス対称有向グラフと見なすが与えられたとき,相互作用グラフとしてGを用いた連言的Booleネットワークにおける不動点の最大数を調べた。Gは誘導4を持たないならば,この量はいくつかの辺を縮約する事によってGから得られた全てのグラフ間のGの最大独立集合の数と最大独立集合の最大数に等しいことを証明した。も,一般的な場合では,これらの等式の一つが成り立つかどうかを判定するためcoNP困難であることを証明し,Gはユニークな誘導4を得た。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 相互作用 ,  有向グラフ ,  不動点 ,  縮約 ,  対称性 ,  *グラフ ,  *ネットワーク
準シソーラス用語： Booleネットワーク , 【Automatic Indexing@JST】

著者キーワード (4件)： Booleネットワーク ,  固定点 ,  最大独立集合 ,  エッジ収縮

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

タイトルに関連する用語 (4件)： 固定点 ,  グラフ ,  収縮 ,  集合