The vertex degrees of minimum spanning trees

被引：7

作者：

Cieslik, D ^{[1
]}

机构：

[1] Univ Greifswald, Inst Math & Comp Sci, D-17487 Greifswald, Germany

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2000年 / 125卷 / 02期

关键词：

graph theory; minimum spanning trees;

D O I：

10.1016/S0377-2217(99)00458-0

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study the problem of minimum spanning trees (MST) with degree constraints. It is well-known that this problem in general is, NP-hard. It will be shown that in finite-dimensional Banach spaces there is a number such that a bounded degree MST can be computed as efficiently as an ordinary MST if the degree constraint is greater than this number. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：278 / 282

页数：5

共 15 条

[1] [Anonymous], 1961, MONATSH MATH
[2] Cheriton D., 1976, SIAM Journal on Computing, V5, P724, DOI 10.1137/0205051
[3] Cieslik D., 1998, STEINER MINIMAL TREE
[4] CIESLIK D, 1998, DIMACS SERIES DISCRE, V40, P59
[5] EFFICIENT ALGORITHMS FOR A FAMILY OF MATROID INTERSECTION PROBLEMS
GABOW, HN
TARJAN, RE
[J]. JOURNAL OF ALGORITHMS, 1984, 5 (01) : 80 - 131
[6] GAREY M, 1980, COMPUTERS INTRACTIBI
[7] TOPOLOGICAL DESIGN OF CENTRALIZED COMPUTER-NETWORKS - FORMULATIONS AND ALGORITHMS
GAVISH, B
[J]. NETWORKS, 1982, 12 (04) : 355 - 377
[8] GRAHAM RL, 1985, ANN HIST COMPUT, V7, P43
[9] GRUNBAUM B, 1961, PAC J MATH, V11, P215
[10] HADWIGER H, 1957, ARCH MATH, V8, P212

← 1 2 →