首页> 美国政府科技报告 >Approximation Algorithm for the Generalized Minimum Spanning Tree Problem with Bounded Cluster Size.

【24h】

Approximation Algorithm for the Generalized Minimum Spanning Tree Problem with Bounded Cluster Size.

机译：有界簇尺寸广义最小生成树问题的逼近算法。

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

Given a complete undirected graph with the nodes partitioned into m node sets called clusters, the Generalized Minimum Spanning Tree problem denoted by GMST's to find a minimum-cost tree which includes exactly one node from each cluster. It is known that the GMST problem is NP-hard and even finding a near optimal solution is NP-hard. The authors give an approximation algorithm for the Generalized Minimum Spanning Tree problem in the case when the cluster size is bounded by p. In this case, the GMST problem can be approximated to within 2p.

著录项

作者
Pop, P. C.; Kern, W.; Still, G.;
展开▼
作者单位

展开▼
年度 2001
页码 1-14
总页数 14
原文格式 PDF
正文语种 eng
中图分类工业技术;
关键词
Mathematics; Geometry; Algorithms; Clusters; Selection; Sequencing; Nodes; Trees(Mathematics); Topology; Approximations; Notations; Theorems; Foreign technology;

机译：mathematics;Geometry;algorithms;Clusters;selection;sequencing;Nodes;Trees(mathematics);Topology;approximations;Notations;Theorems;Foreign technology;

相似文献

外文文献
中文文献
专利

1. A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees [J] . Konemann J., Ravi R. SIAM Journal on Computing . 2002,第6期

机译：一个程度的问题：针对度有界的最小生成树的改进的近似算法
2. Does Determination of Initial Cluster Centroids Improve the Performance of K-Means Clustering Algorithm? Comparison of Three Hybrid Methods by Genetic Algorithm, Minimum Spanning Tree, and Hierarchical Clustering in an Applied Study [J] . Saeedeh Pourahmad, Atefeh Basirat, Amir Rahimi, Computational and mathematical methods in medicine . 2020,第1期

机译：初始簇质心的确定是否提高了K-Means聚类算法的性能？应用研究中遗传算法，最小生成树和分层聚类的三种混合方法的比较
3. Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem [J] . Guimaraes Dilson Almeida, da Cunha Alexandre Salles, Pereira Dilson Lucas European Journal of Operational Research . 2020,第1期

机译：SemideFinite编程下限和分支和绑定算法，用于二次最小生成树问题
4. A Probabilistic Analysis of an Approximation Algorithm for the Minimum Weight Spanning Tree Problem with Bounded from Below Diameter [C] . E. Kh. Gimadi, A. I. Serdyukov Symposium on Operations Research . 2000

机译：近似跨度跨越树问题的近似算法的概率分析
5. Distributed approximation algorithms for minimum spanning trees and other related problems with applications to wireless ad hoc networks [D] . Khan, Md Abdul Maleq 2007

机译：分布式近似算法，用于最小生成树和其他相关问题，应用于无线自组织网络
6. Does Determination of Initial Cluster Centroids Improve the Performance of K-Means Clustering Algorithm? Comparison of Three Hybrid Methods by Genetic Algorithm Minimum Spanning Tree and Hierarchical Clustering in an Applied Study [O] . Saeedeh Pourahmad, Atefeh Basirat, Amir Rahimi, 2020

机译：初始簇质心的确定是否提高了K-Means聚类算法的性能？应用研究中遗传算法最小生成树和分层聚类的三种混合方法的比较
7. An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size [O] . Pop P.C., Kern W., Still G.J. 2001

机译：有界簇大小的广义最小生成树问题的近似算法

Approximation Algorithm for the Generalized Minimum Spanning Tree Problem with Bounded Cluster Size.

摘要

著录项

相似文献

相关主题

期刊订阅