文献

J-GLOBAL ID：201602004325891966   整理番号：74A0222803

サークルグラフの最大クリークおよび最大独立集合を見出すアルゴリズム

Algorithms for a maximum clique and a maximum independent set of a circle graph.

著者 (1件)： GAVRIL F
資料名： Networks  (Networks)
巻： 3  号： 3  ページ： 261-273  発行年： 1973年 
JST資料番号： E0727A  ISSN： 0028-3045  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 一つの閉路およびその上の節点間を結ぶ枝(コードと呼ぶ)からなるグラフを,平面上に閉路を円にコードを直線で描く。 これに対して次のようなグラフをサークルグラフという。その節点は原グラフのコードに1:1対応し,各二つのコードが交わるとき,そのときに限り対応する2節点を枝で結ぶ。本文はサークルグラフにおける極大完全部分グラフ(クリーク)の最大のものおよび互に隣接しない節点部分集合(独立節点集合)の最大のものを見出す効率的な,すなわち節点数の3乗以下に比例する手数のアルゴリズムを与えた;写図4参7

シソーラス用語： アルゴリズム ,  グラフ ,  グラフ理論

タイトルに関連する用語 (5件)： サークル ,  グラフ ,  最大クリーク ,  集合 ,  アルゴリズム