文献

J-GLOBAL ID：201702265857127843   整理番号：17A1597923

内部ノードが制限する最小スパニング木アルゴリズムの研究【JST・京大機械翻訳】

Algorithm for minimum internal nodes constrained spanning tree problem

著者 (4件)： Jiang Xiaojuan (杭州電子科技大学 理学院,杭州,310018) ,  Zhang An (杭州電子科技大学 理学院,杭州,310018) ,  Chen Yong (杭州電子科技大学 理学院,杭州,310018) ,  Chen Guangting (台州学院,浙江 台州,317000)
資料名： Jisuanji Gongcheng yu Yingyong  (Jisuanji Gongcheng yu Yingyong)
号： 10  ページ： 35-37  発行年： 2017年 
JST資料番号： C2533A  ISSN： 1002-8331  CODEN： JGYYAT  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： 内部ノードによって制限された最小スパニング木の問題を研究した。本論文では,重み関数が三角形不等式を満たし,固定点集合Vの一つの部分集合R(頂点の重みが最小の生成木)を与えるために,近似多項式2の多項式時間近似アルゴリズムを提案し,その近似比がコンパクトであることを示した。 V,E,w:E→R+を辺集合Eと仮定する.Vは,図Gを満たす1つのRを満たす点が内部であることを目標としている.Data from Wanfang. Translated by JST【JST・京大機械翻訳】

シソーラス用語： 重み関数 ,  近似法 ,  不等式 ,  多項式 ,  *スパンニング木 ,  *アルゴリズム ,  部分集合
準シソーラス用語： 近似アルゴリズム ,  多項式時間 ,  点集合 , 【Automatic Indexing@JST】

著者キーワード (4件)： undirected weighted graph ,  spanning tree ,  approximation algorithm ,  performance ratio

分類 (3件)： 計算理論  (JB02000A) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  産業用ロボット  (IC04020M)

タイトルに関連する用語 (5件)： ノード ,  制限 ,  スパニング木 ,  アルゴリズム ,  研究