文献

J-GLOBAL ID：202002287454428500   整理番号：20A1124444

部分的逆最大スパンニング木問題のための近似アルゴリズム【JST・京大機械翻訳】

Approximation algorithms for capacitated partial inverse maximum spanning tree problem

著者 (5件)： Li Xianyue (School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu, People’s Republic of China) ,  Zhang Zhao (College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua, Zhejiang, People’s Republic of China) ,  Yang Ruowang (School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu, People’s Republic of China) ,  Zhang Heping (School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu, People’s Republic of China) ,  Du Ding-Zhu (Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA)
資料名： Journal of Global Optimization  (Journal of Global Optimization)
巻： 77  号： 2  ページ： 319-340  発行年： 2020年 
JST資料番号： W2010A  ISSN： 0925-5001  CODEN： JGOPEO  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： エッジ重み付きグラフと非巡回エッジ集合を与えて,部分逆最大スパンニング木問題の目標は,与えられたエッジ集合を含む新しい重み関数に関して最大スパンニング木が存在するように,重み関数をできるだけ修正することである。本論文では,pが整数と[数式:原文を参照]である[数式:原文を参照]ノルムの下で容量制約を持つこの問題を考察した。最初に,この問題の実行可能な解を特性化した。次に,重み関数を減少させることができるとき,この問題に対する[数式:原文を参照]近似アルゴリズムを提示した。ここで,kは与えられたエッジ集合におけるエッジの数である。最後に,重み関数を減少させ,増加させることができる場合,一般的な場合に対する近似アルゴリズムを提案し,その近似比を解析した。さらに,これらのアルゴリズムが重み付き[数式:原文を参照]ノルムと加重和Hamming距離の下で一般化できることを示した。Copyright Springer Science+Business Media, LLC, part of Springer Nature 2019 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  *近似法 ,  逆問題 ,  キャラクタリゼーション ,  重み関数 ,  *スパンニング木 ,  ノルム ,  Hamming距離
準シソーラス用語： *近似アルゴリズム ,  巡回 ,  容量制約 , 【Automatic Indexing@JST】

著者キーワード (3件)： 部分逆問題 ,  スパンニング木 ,  近似アルゴリズム

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： スパンニング木 ,  問題 ,  近似アルゴリズム