文献

J-GLOBAL ID：202002223808492365   整理番号：20A2085278

最大k辺彩色クラスタリング問題のための0.3622近似アルゴリズム【JST・京大機械翻訳】

A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem

著者 (2件)： Ageev Alexander (Sobolev Institute of Mathematics, Novosibirsk, Russia) ,  Kononov Alexander (Sobolev Institute of Mathematics, Novosibirsk, Russia)
資料名： Communications in Computer and Information Science  (Communications in Computer and Information Science)
巻： 1275  ページ： 3-15  発行年： 2020年 
JST資料番号： W5071A  ISSN： 1865-0929  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： Max k-Edge-Coloredクラスタリング問題(MAX-k-ECと略称)において,無向グラフとk色を与えた。グラフの各エッジは色と負の重みを持つ。目標は,その色がそれらの終点の色と一致するエッジの全重みを最大化するように頂点をカラーすることである。問題をAngelら[3]によって導入した。本論文では,AlhamdanとKononov[2]によって確立された最良の以前に知られている近似結合[数式:原文を参照]を大幅に改善する近似因子[数式:原文を参照]を有するMAX-k-ECのための多項式時間アルゴリズムを与えた。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *近似法 ,  *クラスタ化 ,  略語 ,  無向グラフ ,  緩和現象 ,  *発色
準シソーラス用語： *近似アルゴリズム ,  Max ,  エンドポイント ,  多項式時間アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (5件)： クラスタリング問題 ,  エッジ彩色グラフ ,  線形緩和 ,  近似アルゴリズム ,  最悪ケース解析

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

タイトルに関連する用語 (4件)： 彩色 ,  クラスタリング ,  問題 ,  近似アルゴリズム