期刊
SIAM JOURNAL ON COMPUTING
卷 33, 期 3, 页码 608-631出版社
SIAM PUBLICATIONS
DOI: 10.1137/S0097539701393384
关键词
spanners; graph algorithms; graph partitions
An (alpha,beta)-spanner of a graph G is a subgraph H such that dist(H)(u,w)less than or equal toalpha. distt(G)(u,w)+beta for every pair of vertices u,w, where dist(G') (u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible (2kappa-1,0)-spanner (also known as multiplicative (2kappa-1)-spanner) of size O(n(1+1/kappa)) for every integer kappagreater than or equal to1, and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size (O) over tilde (n(3/2)). This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant epsilon, lambda>0 there exists a constant beta=beta(epsilon,lambda) such that for every n-vertex graph G there is an efficiently constructible (1 +epsilon,beta)-spanner of size O(n(1+lambda)).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据