Cut and patch Steiner trees for ladders

被引：3

作者：

Burkard, RE ^{[1
]}

Dudas, T ^{[1
]}

Maier, T ^{[1
]}

机构：

[1] GRAZ TECH UNIV,INST MATH B,A-8010 GRAZ,AUSTRIA

来源：

DISCRETE MATHEMATICS | 1996年 / 161卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(95)00275-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper we deal with the Steiner minimal tree problem for a special type of point sets called ladders. We give a counterexample to the so-called 'cut and patch tree method' described in several former papers. Moreover, we explain how to modify this method such that it provides always an optimal solution.

引用

页码：53 / 61

页数：9

共 13 条

[1]

[Anonymous], 1961, CAN MATH BULLETIN, DOI DOI 10.4153/CMB-1961-016-2

[2]

Chung F.R.K, 1989, MATH MAG, V62, P83, DOI 10.2307/2690388

[3]

Chung F. R. K., 1978, ANN DISCRETE MATH, V2, P173, DOI 10.1016/S0167-5060(08)70332-7

[4]

DU DZ, 1985, P AM MATH SOC, V95, P613

[5]

DU DZ, 1983, T AM MATH SOC, V278, P149

[6] STEINER MINIMAL-TREES FOR REGULAR POLYGONS [J].

DU, DZ ;

HWANG, FK ;

WENG, JF .

DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (01) :65-84

[7] STEINER MINIMAL-TREES ON SETS OF 4 POINTS [J].

DU, DZ ;

HWANG, FK ;

SONG, GD ;

TING, GY .

DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (04) :401-414

[8]

DU DZ, 1987, ACTA MATH APPL SIN-E, V3, P246

[9] COMPLEXITY OF COMPUTING STEINER MINIMAL TREES [J].

GAREY, MR ;

GRAHAM, RL ;

JOHNSON, DS .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) :835-859

[10]

HWANBG FK, 1992, ANN DISCRETE MATH, V53, P68

← 1 2 →