NEAR-LINEAR TIME CONSTRUCTION OF SPARSE NEIGHBORHOOD COVERS

Authors
AWERBUCH B BERGER B COWEN L PELEG D
Citation
B. Awerbuch et al., NEAR-LINEAR TIME CONSTRUCTION OF SPARSE NEIGHBORHOOD COVERS, SIAM journal on computing (Print), 28(1), 1999, pp. 263-277
Citations number
27
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing (Print) → ACNP
ISSN journal
00975397
Volume
28
Issue
1
Year of publication
1999
Pages
263 - 277
Database
ISI
SICI code
0097-5397(1999)28:1<263:NTCOSN>2.0.ZU;2-Y
Abstract
This paper introduces a near-linear time sequential algorithm for cons tructing a sparse neighborhood cover. This implies analogous improveme nts (from quadratic to near-linear time) for any problem whose solutio n relies on network decompositions, including small edge cuts in plana r graphs, approximate shortest paths, and weight- and distance-preserv ing graph spanners. In particular, an O(log n) approximation to the k- shortest paths problem on an n-vertex, E-edge graph is obtained that r uns in (O) over tilde (n + E + k) time.