文献

J-GLOBAL ID：201802275569319197   整理番号：18A0091907

抽出と後方展開探索を用いた大規模グラフのための最小和彩色【Powered by NICT】

Minimum sum coloring for large graphs with extraction and backward expansion search

著者 (5件)： Wu Qinghua (School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China) ,  Zhou Qing (School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China) ,  Jin Yan (School of Computer Science, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China) ,  Hao Jin-Kao (LERIA, Universite d’Angers, 2 Boulevard Lavoisier, 49045 Angers, France) ,  Hao Jin-Kao (Institut Universitaire de France, 1 Rue Descartes, 75231 Paris, France)
資料名： Applied Soft Computing  (Applied Soft Computing)
巻： 62  ページ： 1056-1065  発行年： 2018年 
JST資料番号： W2175A  ISSN： 1568-4946  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最小和彩色問題(MSCP)は古典的な頂点彩色問題(VCP)に密接に関連するモデルである。MSCPはNP困難であることが知られており,従って大規模グラフのための問題を解く特に挑戦的である。一般的な「減少と解」原理に基づき,VCPの研究に触発されて,大規模グラフにMSCPに対する上限と下限を計算するための抽出と後方膨張探索法(EBES)を提案した。抽出相は大きなコレクション対の分離した大きな独立集合(または色クラス)を抽出することにより与えられたグラフを減少させた。後方拡張相は各中間グラフの和彩色を最適化しながら,中間グラフを回収するために抽出された独立集合を追加した。DIMACSと色グラフ彩色競争から450 4000頂点を持つ35種の大きなベンチマークグラフの集合上で提案アプローチを評価した。計算結果はEBESは19グラフのための改良された上限を見出すことができ,12グラフのための下限を改善することを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 最適化 ,  *グラフ ,  NP困難 ,  *発色 ,  彩色問題
準シソーラス用語： グラフ彩色 ,  探索法 , 【Automatic Indexing@JST】

著者キーワード (4件)： 彩色問題 ,  ハイブリッド探索 ,  独立集合 ,  問題還元

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： 展開 ,  探索 ,  大規模 ,  グラフ ,  彩色