ON THE MINIMUM DIAMETER SPANNING TREE PROBLEM

被引：68

作者：

HASSIN, R

TAMIR, A

机构：

[1] Department of Statistics and Operations Research, School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv

来源：

INFORMATION PROCESSING LETTERS | 1995年 / 53卷 / 02期

关键词：

ALGORITHMS; COMBINATORIAL PROBLEMS; MINIMUM DIAMETER SPANNING TREE; ABSOLUTE; 1-CENTER;

D O I：

10.1016/0020-0190(94)00183-Y

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We point out a relation between the minimum diameter spanning tree of a graph and its absolute 1-center. We use this relation to solve the diameter problem and an extension of its efficiently.

引用

页码：109 / 111

页数：3

共 10 条

[1]

CUNNIGHAMEGREEN.RA, 1984, DISCRETE APPL MATH, V7, P275

[2]

FREDMAN M, 1987, J ACM, V34, P1004

[3]

Hakimi S. L., 1978, Transportation Science, V12, P1, DOI 10.1287/trsc.12.1.1

[4] OPTIMUM LOCATIONS OF SWITCHING CENTERS + ABSOLUTE CENTERS + MEDIANS OF GRAPH [J].

HAKIMI, SL .

OPERATIONS RESEARCH, 1964, 12 (03) :450-&

[5]

Handler G. Y., 1973, Transportation Science, V7, P287, DOI 10.1287/trsc.7.3.287

[6] MINIMUM DIAMETER SPANNING-TREES AND RELATED PROBLEMS [J].

HO, JM ;

LEE, DT ;

CHANG, CH ;

WONG, CK .

SIAM JOURNAL ON COMPUTING, 1991, 20 (05) :987-997

[7]

Ihler E, 1991, LNCS, V551, P103

[8] ALGORITHMIC APPROACH TO NETWORK LOCATION PROBLEMS .1. P-CENTERS [J].

KARIV, O ;

HAKIMI, SL .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1979, 37 (03) :513-538

[9] CENTERS AND MEDIANS OF A GRAPH [J].

MINIEKA, E .

OPERATIONS RESEARCH, 1977, 25 (04) :641-650

[10]

Tamir A., 1988, SIAM J DISCRETE MATH, V1, P377

← 1 →