计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2009年
6期
1052-1057
,共6页
有向无环图%生成树%近似算法%最小度%优化
有嚮無環圖%生成樹%近似算法%最小度%優化
유향무배도%생성수%근사산법%최소도%우화
计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈ V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过△*+1,其中△*为某一最优树的度.算法的时间复杂度为O(n2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多.
計算具有較小度的生成樹是算法與複雜性研究的一箇基本問題,同時在網絡設計等領域具有重要應用.給定具有n箇頂點的有嚮無環圖G=(V,E)和根頂點r∈ V,最小度生成樹問題欲求一棵以r為根的生成樹T,使得在G的所有以r為根的生成樹中T的最大度最小.給齣該問題的一種迭代的多項式時間近似算法.該算法所求樹的度不超過△*+1,其中△*為某一最優樹的度.算法的時間複雜度為O(n2logn),其中n為頂點數目.算法沒有運用過多的枚舉,其實際運行時間要快得多.
계산구유교소도적생성수시산법여복잡성연구적일개기본문제,동시재망락설계등영역구유중요응용.급정구유n개정점적유향무배도G=(V,E)화근정점r∈ V,최소도생성수문제욕구일과이r위근적생성수T,사득재G적소유이r위근적생성수중T적최대도최소.급출해문제적일충질대적다항식시간근사산법.해산법소구수적도불초과△*+1,기중△*위모일최우수적도.산법적시간복잡도위O(n2logn),기중n위정점수목.산법몰유운용과다적매거,기실제운행시간요쾌득다.
