Loading...
Please wait, while we are loading the content...
Similar Documents
All-pairs nearly 2-approximate shortest paths in o(n2poly logn) time
| Content Provider | CiteSeerX |
|---|---|
| Author | Baswana, Surender Goyal, Vishrut Sen, Sandeep |
| Abstract | Let G = (V,E) be an unweighted undirected graph on V = n vertices and E = m edges. Let δ(u, v) denote the distance between vertices u, v ∈ V. An algorithm is said to compute all-pairs t-approximate shortest-paths/distances, for some t ≥ 1, if for each pair of vertices u, v ∈ V, the path/distance reported by the algorithm is not longer/greater than t · δ(u, v). This paper presents two extremely simple randomized algorithms for computing all-pairs nearly 2-approximate distances. The first algorithm requires expected O(m2/3n logn + n2) time, and for any u, v ∈ V reports distance no greater than 2δ(u, v) + 1. Our second algorithm requires expected O(n2 log3/2 n) time, and for any u, v ∈ V reports distance bounded by 2δ(u, v) + 3. 1 |
| File Format | |
| Journal | Theor. Comput. Sci |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | N2poly Logn 2-approximate Shortest Path Report Distance Logn N2 Second Algorithm All-pairs T-approximate Shortest-paths Distance 2-approximate Distance First Algorithm N2 Log3 Unweighted Undirected Graph Path Distance Simple Randomized Algorithm |
| Content Type | Text |
| Resource Type | Article |
