ﻻ يوجد ملخص باللغة العربية
Let $G = (V,E,w)$ be a weighted, digraph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed source $s$ and the goal is to maintain a data structure that can answer path-queries $s rightarrowtail v$ for any $v in V$. In the more general single-source shortest paths (SSSP) problem the goal is to return an approximate shortest path to $v$, and in the SCC problem the goal is to maintain strongly connected components of $G$ and to answer path queries within each component. All of these problems have been very actively studied over the past two decades, but all the fast algorithms are randomized and, more significantly, they can only answer path queries if they assume a weaker model: they assume an oblivious adversary which is not adaptive and must fix the update sequence in advance. This assumption significantly limits the use of these data structures, most notably preventing them from being used as subroutines in static algorithms. All the above problems are notoriously difficult in the adaptive setting. In fact, the state-of-the-art is still the Even and Shiloach tree, which dates back all the way to 1981 and achieves total update time $O(mn)$. We present the first algorithms to break through this barrier: 1) deterministic decremental SSR/SCC with total update time $mn^{2/3 + o(1)}$ 2) deterministic decremental SSSP with total update time $n^{2+2/3+o(1)}$. To achieve these results, we develop two general techniques of broader interest for working with dynamic graphs: 1) a generalization of expander-based tools to dynamic directed graphs, and 2) a technique that we call congestion balancing and which provides a new method for maintaining flow under adversarial deletions. Using the second technique, we provide the first near-optimal algorithm for decremental bipartite matching.
In the decremental single-source shortest paths (SSSP) problem, the input is an undirected graph $G=(V,E)$ with $n$ vertices and $m$ edges undergoing edge deletions, together with a fixed source vertex $sin V$. The goal is to maintain a data structur
In the decremental $(1+epsilon)$-approximate Single-Source Shortest Path (SSSP) problem, we are given a graph $G=(V,E)$ with $n = |V|, m = |E|$, undergoing edge deletions, and a distinguished source $s in V$, and we are asked to process edge deletion
We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. The input to the problem is an $n$-vertex $m$-edge graph $G$ with non-negative edge lengths, that undergoes a sequence of edge deletions. The goal is
In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph $G$ and a source node $s$ the goal is to maintain shortest distances between $s$ and all other nodes in $G$ under a sequence of online adversar
In this thesis, we present new techniques to deal with fundamental algorithmic graph problems where graphs are directed and partially dynamic, i.e. undergo either a sequence of edge insertions or deletions: - Single-Source Reachability (SSR), - S