文献

J-GLOBAL ID：202002212470568417   整理番号：20A0610655

重み付き二分グラフの色コスト彩色【JST・京大機械翻訳】

Chromatic cost coloring of weighted bipartite graphs

著者 (2件)： Pikies Tytus (Department of Algorithms and System Modelling, ETI Faculty, Gdansk University of Technology, Gabriela Narutowicza 11/12, Gdansk 80-233, Poland) ,  Kubale Marek (Department of Algorithms and System Modelling, ETI Faculty, Gdansk University of Technology, Gabriela Narutowicza 11/12, Gdansk 80-233, Poland)
資料名： Applied Mathematics and Computation  (Applied Mathematics and Computation)
巻： 375  ページ： Null  発行年： 2020年 
JST資料番号： D0568B  ISSN： 0096-3003  CODEN： AMHCBQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフGとカラーコストCのシーケンスを与えると,CostColoring最適化問題は,Cに関して最小の総コストでGの着色を見つけることにある。重み付き二部グラフに関するこの問題の解析を示した。ここでは,色コストの有限系列がNP困難であることを特定し,他の有限系列に対する正確な多項式アルゴリズムを提案した。次に,これらの結果を無限シーケンスの実質的クラスに拡張した。著者らは,これらの結果が部分的に非加重二部グラフに移動することを示した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 着色 ,  *発色 ,  総原価 ,  最適化問題 ,  NP困難
準シソーラス用語： *二部グラフ , 【Automatic Indexing@JST】

著者キーワード (6件)： 色コスト着色 ,  最適コスト色分配 ,  加重グラフ ,  2部グラフ ,  近似アルゴリズム ,  色コスト3-擬カラーリング

分類 (1件)： 数値計算  (JE02000J)

タイトルに関連する用語 (3件)： グラフ ,  色 ,  彩色