文献

J-GLOBAL ID：201302263307316418   整理番号：13A0990111

グラフのk-虹支配番号を発見するためのタブー探索アルゴリズム

A Tabu Search Algorithm for Finding k-Rainbow Domination Numbers of Graphs

著者 (1件)： ZHAO Taiyin (Univ. Electronic Sci. and Technol. China, Chengdu, CHN)
資料名： Journal of Computational and Theoretical Nanoscience  (Journal of Computational and Theoretical Nanoscience)
巻： 10  号： 3  ページ： 651-654  発行年： 2013年03月 
JST資料番号： W2377A  ISSN： 1546-1955  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本報では,k色の集合のサブ集合を,グラフGのバーテックスに割り当てるものと仮定する。空集合を割り当てられたバーテックスが,その近傍に全てのk色を所有することを求められる場合には,この割り当てをグラフGのk-虹支配関数と呼ぶ。そして,これに対応する不変量γ_rk(G)の集合を,Gのk-虹支配番号と呼ぶ。本報では,38≦n≦47および5≦n≦24の,それぞれの一般化Petersenグラフ,P(n,3)およびP(n,2)に対応する2-虹支配番号および3-虹支配番号の上界を発見するために,タブー探索アルゴリズムを提案した。実験によってそのすぐれた性能を明らかにし,Matlabの支援に基づいて,n≦15に対するP(n,3)の正確なγ_r2を発見した。

シソーラス用語： *色 ,  *タブー探索 ,  アルゴリズム ,  *発見的方法 ,  最適化 ,  限界 ,  近似法 ,  最適化手法
準シソーラス用語： k-虹支配番号 ,  タブー探索アルゴリズム ,  *ヒューリスティック ,  上界

分類 (3件)： 数値解析,近似法  (AB04000F) ,  色  (BD03090A) ,  システム最適化手法  (IA02050Z)

タイトルに関連する用語 (6件)： グラフ ,  虹 ,  支配 ,  番号 ,  発見 ,  タブー探索アルゴリズム