Approximate Shortest Paths Avoiding a Failed Vertex: Near Optimal Data Structures for Undirected Unweighted Graphs

被引：0
作者：
Surender Baswana
Neelesh Khanna
机构：
[1] IIT Kanpur,Department of Computer Science and Engineering
[2] Oracle India Pvt. Ltd.,undefined
来源：
Algorithmica | 2013年 / 66卷
关键词：
Shortest path; Distance; Approximate distance; Oracle;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Let G=(V,E) be an undirected unweighted graph. A path between any two vertices u,v∈V is said to be t-approximate shortest path if its length is at most t times the length of the shortest path between u and v. We address the problem of building a compact data structure which can efficiently answer the following query for any u,v,x∈V and t>1: Reportt-approximate shortest path betweenuandvwhen vertexxfails.
引用
收藏
页码：18 / 50
页数：32
相关论文
共 41 条
  • [1] Aingworth D.(1999)Fast estimation of diameter and shortest paths (without matrix multiplication) SIAM J. Comput. 28 1167-1181
  • [2] Chekuri C.(2010)Faster algorithms for all-pairs approximate shortest paths in undirected graphs SIAM J. Comput. 39 2865-2896
  • [3] Indyk P.(2006)Approximate distance oracles for unweighted graphs in expected O( ACM Trans. Algorithms 2 557-577
  • [4] Motwani R.(2001)) time J. Algorithms 38 335-353
  • [5] Baswana S.(2004)All-pairs small-stretch paths J. ACM 51 968-992
  • [6] Kavitha T.(2008)A new approach to dynamic all pairs shortest paths SIAM J. Comput. 37 1299-1318
  • [7] Baswana S.(2000)Oracles for distances avoiding a failed node or link SIAM J. Comput. 29 1740-1759
  • [8] Sen S.(1987)All-pairs almost shortest paths J. ACM 34 596-615
  • [9] Cohen E.(1984)Fibonacci heaps and their uses in improved network optimization problem SIAM J. Comput. 13 338-355
  • [10] Zwick U.(2007)Fast algorithms for finding nearest common ancestors ACM Trans. Algorithms 3 123-139
12345