Computing almost shortest paths
Copyright policy )Computing almost shortest paths
We study the <i>s-sources almost shortest paths</i> (abbreviated <i>s-ASP</i>) problem. Given an unweighted graph <i>G</i> = (<i>V,E</i>), and a subset <i>S</i> ⊆ <i>V</i> of <i>s</i> nodes, the goal is to compute almost shortest paths between all the pairs of nodes <i>S</i> × <i>V</i>. We devise an algorithm with running time <i>O</i>(∣<i>E</i>∣<i>n</i><sup>ρ</sup> + <i>s</i> · <i>n</i><sup>1 + ζ)</sup> for this problem that computes the paths <i>P</i><sub><i>u,w</i></sub> for all pairs (<i>u,w</i>) ∈ <i>S</i> × <i>V</i> such that the length of <i>P</i><sub><i>u,w</i></sub> is at most (1 + ε) <i>d</i><sub><i>G</i></sub>(<i>u,w</i>) + β(ζ,ρ,ε), and β(ζ,ρ,ε) is constant when ζ, ρ, and ε are arbitrarily small constants. We also devise a distributed protocol for the <i>s</i>-ASP problem that computes the paths <i>P</i><inf><i>u,w</i></inf> as above, and has time and communication complexities of <i>O</i>(<i>s</i> · <i>Diam(G)</i> + <i>n</i><sup>1 + ζ/2</sup>) (respectively, <i>O</i>(<i>s</i> · <i>Diam(G)</i> log<sup>3</sup> <i>n</i> + <i>n</i><sup>1 + ζ/2</sup> log <i>n</i>)) and <i>O</i>(∣<i>E</i>∣ <i>n</i><sup>ρ</sup> + <i>s</i> · <i>n</i><sup>1 + ζ)</sup> (respectively, <i>O</i>(∣<i>E</i>∣ <i>n</i><sup>ρ</sup> + <i>s</i> · <i>n</i><sup>1 + ζ</sup> + <i>n</i><sup>1 + ρ + ζ(ρ − ζ/2)/2)) in the synchronous (respectively asynchronous) setting. Our sequential algorithm, as well as the distributed protocol, is based on a novel algorithm for constructing (1 + ε, β(ζ,ρ, ε))-spanners of size <i>O</i>(<i>n</i><sup>1 + ζ</sup>), developed in this article. This algorithm has running time of <i>O</i>(∣<i>E</i>∣ <i>n</i><sup>ρ</sup>), which is significantly faster than the previously known algorithm given in Elkin and Peleg [2001], whose running time is <i>Õ</i>(<i>n</i><sup>2 + ρ</sup>). We also develop the first distributed protocol for constructing (1 + ε,β)-spanners. The communication complexity of this protocol is near optimal.
- Weizmann Institute of Science Israel
- Yale University United States
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).103 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!