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

DOI10.4230/LIPICS.STACS.2016.18MaRDI QIDQ4601870zbMATH OpenOpenAlexFDO

Authors D. Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti

Publication date 24 January 2018

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

zbMATH Keywords

distance oraclefault-tolerant shortest-path treeminimum spanning tree

Mathematics Subject Classification ID

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

Abstract: Let $G$ be an $n$-node and $m$-edge positively real-weighted undirected graph. For any given integer $fge1$, we study the problem of designing a sparse emph{f-edge-fault-tolerant} ($f$-EFT) $sigma${em -approximate single-source shortest-path tree} ($sigma$-ASPT), namely a subgraph of $G$ having as few edges as possible and which, following the failure of a set $F$ of at most $f$ edges in $G$, contains paths from a fixed source that are stretched at most by a factor of $sigma$. To this respect, we provide an algorithm that efficiently computes an $f$-EFT $(2|F|+1)$-ASPT of size $O(fn)$. Our structure improves on a previous related construction designed for emph{unweighted} graphs, having the same size but guaranteeing a larger stretch factor of $3(f+1)$, plus an additive term of $(f+1)logn$. Then, we show how to convert our structure into an efficient $f$-EFT emph{single-source distance oracle} (SSDO), that can be built in $widetildeO(fm)$ time, has size $O(fnlo{g}^{2}n)$, and is able to report, after the failure of the edge set $F$, in $O(|F{|}^{2}lo{g}^{2}n)$ time a $(2|F|+1)$-approximate distance from the source to any node, and a corresponding approximate path in the same amount of time plus the path's size. Such an oracle is obtained by handling another fundamental problem, namely that of updating a emph{minimum spanning forest} (MSF) of $G$ after that a emph{batch} of $k$ simultaneous edge modifications (i.e., edge insertions, deletions and weight changes) is performed. For this problem, we build in $O(mlo{g}^{3}n)$ time a emph{sensitivity} oracle of size $O(mlo{g}^{2}n)$, that reports in $O(k^{2}lo{g}^{2}n)$ time the (at most $2k$) edges either exiting from or entering into the MSF. [...]

Recommendations

• Multiple-edge-fault-tolerant approximate shortest-path trees
• Fault-tolerant approximate shortest-path trees
• Fault-tolerant approximate shortest-path trees
• Path-fault-tolerant approximate shortest-path trees
• scientific article; zbMATH DE number 913359
• Fault-tolerant approximate BFS structures
• Approximate Single-Source Fault Tolerant Shortest Path
• Fault Tolerant Approximate BFS Structures
• scientific article; zbMATH DE number 6850433
• Sparse fault-tolerant BFS trees

Cited in

(21)

• Fault-tolerant approximate shortest-path trees
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Output sensitive fault tolerant maximum matching
• Efficient oracles and routing schemes for replacement paths
• Path-fault-tolerant approximate shortest-path trees
• Fault-tolerant subgraph for single-source reachability: general and optimal
• scientific article; zbMATH DE number 6850433 (Why is no real title available?)
• Conditional hardness for sensitivity problems
• scientific article; zbMATH DE number 913359 (Why is no real title available?)
• Generic single edge fault tolerant exact distance oracle
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• Sparse weight tolerant subgraph for single source shortest path
• Fault Tolerant Approximate BFS Structures
• Improved approximations for relative survivable network design
• An efficient strongly connected components algorithm in the fault tolerant model
• New extremal bounds for reachability and strong-connectivity preservers under failures
• New fault tolerant subset preservers
• New extremal bounds for reachability and strong-connectivity preservers under failures
• Near optimal algorithm for fault tolerant distance oracle and single source replacement path problem
• Fault-tolerant bounded flow preservers
• Incremental distance products via faulty shortest paths

This page was built for publication: Multiple-edge-fault-tolerant approximate shortest-path trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601870)