文献

J-GLOBAL ID：201702238788264427   整理番号：17A0889702

超グラフ彩色に基づく制約を持つIPOGの垂直成長の最適化【Powered by NICT】

Optimizing IPOG’s Vertical Growth with Constraints Based on Hypergraph Coloring

著者 (5件)： Duan Feng ,  Lei Yu ,  Yu Linbin ,  Kacker Raghu N. ,  Kuhn D. Richard
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： ICSTW  ページ： 181-188  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本論文では,制約の存在下におけるIPOGの垂直成長相の最適化を提示した。垂直成長問題は「最小頂点彩色」と呼ばれる古典的なNP困難グラフ問題としてモデル化した。グラフモデルでは,頂点が着色を待っているか失われたタプルまたは初期状態,エッジ/超辺で種々の色の着色されている既存の試験は同じ試験にできない頂点競合した。着色後,同じ色の頂点の群は厳密に有効な試験に変換することができる。元IPOGアルゴリズムは垂直成長の間失われたタプルをカバーする任意次数を用いているので,試験の数を低減するために,著者らは,各タプルのコンフリクト(DOC)の程度を計算し,DOCの非増加次数のタプルをカバーしている。はこの最適化を組み込んだ新しいIPOGアルゴリズムを実装した。実験結果は,新しいIPOGアルゴリズム制約条件を持つ多くの現実のシステムのための試験の数を低減することを示した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： NP困難 ,  *グラフ ,  着色 ,  *最適化 ,  モデリング ,  アルゴリズム ,  *発色
準シソーラス用語： 次数 ,  初期状態 ,  グラフモデル ,  *グラフ彩色 , 【Automatic Indexing@JST】

分類 (2件)： グラフ理論基礎  (IA02020S) ,  図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (5件)： グラフ彩色 ,  制約 ,  垂直 ,  成長 ,  最適化