On resilient graph spanners

DOI10.1007/s00453-015-0006-xzbMath1339.68198arXiv1303.1559OpenAlexW2157278899WikidataQ61609279 ScholiaQ61609279MaRDI QIDQ289925

Andrea Ribichini, Giuseppe F. Italiano, Giorgio Ausiello, Paolo Giulio Franciosa

Publication date: 31 May 2016

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph spannersfault tolerancegraph algorithmsalgorithm complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Improved Purely Additive Fault-Tolerant Spanners, Graph spanners: a tutorial review, Fault-tolerant approximate shortest-path trees, Multiple-edge-fault-tolerant approximate shortest-path trees

Uses Software

• spanner

Cites Work

• Unnamed Item
• Graph spanners in the streaming model: An experimental study
• On sparse spanners of weighted graphs
• Cycles of even length in graphs
• Fault-tolerant spanners
• COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING
• Additive spanners and (α, β)-spanners
• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
• Fully dynamic randomized algorithms for graph spanners
• Sparse Sourcewise and Pairwise Distance Preservers
• Oracles for Distances Avoiding a Failed Node or Link
• Graph spanners
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• All-Pairs Almost Shortest Paths
• Fault Tolerant Additive Spanners
• Small Stretch Spanners on Dynamic Graphs
• Fault Tolerant Spanners for General Graphs
• Dynamic Algorithms for Graph Spanners
• Network Analysis
• Network Analysis
• Automata, Languages and Programming
• New Additive Spanners
• On a problem of K. Zarankiewicz
• Algorithmic mechanism design