Path-Fault-Tolerant Approximate Shortest-Path Trees

DOI10.1007/978-3-319-25258-2_16zbMath1471.68036arXiv1507.01695OpenAlexW2963892009MaRDI QIDQ3460718

Stefano Leucci, Annalisa D'Andrea, Mattia D'Emidio, Guido Proietti, Daniele Frigioni

Publication date: 8 January 2016

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.01695

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items

Fault-tolerant approximate shortest-path trees ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees

Cites Work

• Unnamed Item
• Unnamed Item
• Swapping a failing edge of a single source shortest paths tree is good and fast
• Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
• Exact and approximate truthful mechanisms for the shortest paths tree problem
• Dynamically Maintaining Shortest Path Trees under Batches of Updates
• Fault-Tolerant Approximate Shortest-Path Trees
• Approximate distance oracles for unweighted graphs in expected O ( n ² ) time
• Emergence of Scaling in Random Networks
• Fast Algorithms for Finding Nearest Common Ancestors
• Approximate distance oracles
• f-Sensitivity Distance Oracles and Routing Schemes
• Fault-Tolerant Approximate BFS Structures
• Fault-tolerant spanners for general graphs
• Approximate distance oracles with constant query time
• Automata, Languages and Programming