ON SPARSE SPANNERS OF WEIGHTED GRAPHS

被引：371

作者：

ALTHOFER, I

DAS, G

DOBKIN, D

JOSEPH, D

SOARES, J

机构：

[1] MEMPHIS STATE UNIV, DEPT MATH SCI, MEMPHIS, TN 38152 USA

[2] PRINCETON UNIV, DEPT COMP SCI, PRINCETON, NJ 08544 USA

[3] UNIV WISCONSIN, DEPT COMP SCI, MADISON, WI 53706 USA

[4] UNIV SAO PAULO, IME, MAC, BR-01498 SAO PAULO, BRAZIL

[5] UNIV CHICAGO, DEPT COMP SCI, CHICAGO, IL 60637 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1993年 / 9卷 / 01期

关键词：

D O I：

10.1007/BF02189308

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a graph G, a subgraph G' is a t-spanner of G if, for every u, v is-an-element-of V, the distance from u to v in G' is at most t times longer than the distance in G. In this paper we give a simple algorithm for constructing sparse spanners for arbitrary weighted graphs. We then apply this algorithm to obtain specific results for planar graphs and Euclidean graphs. We discuss the optimality of our results and present several nearly matching lower bounds.

引用

页码：81 / 100

页数：20

共 26 条

[11]

DAS G, 1989, LECT NOTES COMPUT SC, V401, P168

[12]

Dobkin D. P., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P20, DOI 10.1109/SFCS.1987.18

[13] TREES, TIGHT EXTENSIONS OF METRIC-SPACES, AND THE COHOMOLOGICAL DIMENSION OF CERTAIN GROUPS - A NOTE ON COMBINATORIAL PROPERTIES OF METRIC-SPACES [J].

DRESS, AWM .

ADVANCES IN MATHEMATICS, 1984, 53 (03) :321-402

[14]

Erdos P., 1963, WISS Z U HALLE MATH, V12, P251

[15]

KEIL JM, 1989, LECT NOTES COMPUT SC, V382, P47

[16]

KEIL JM, 1988, LECT NOTES COMPUT SC, V318, P208

[17]

LEVCOPOULOS C, 1989, LECT NOTES COMPUT SC, V401, P9

[18]

Longyear J. Q., 1970, Journal of Combinatorial Theory, Series A, V9, P420, DOI 10.1016/S0021-9800(70)80095-3

[19] RAMANUJAN GRAPHS [J].

LUBOTZKY, A ;

PHILLIPS, R ;

SARNAK, P .

COMBINATORICA, 1988, 8 (03) :261-277

[20]

Margulis G. A., 1988, Problems of Information Transmission, V24, P39

← 1 2 3 →