ﻻ يوجد ملخص باللغة العربية
In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph $G=(V,E,w)$ undergoing edge deletions and a source vertex $r in V$; let $n = |V|, m = |E|$ and $W$ be the aspect ratio of the graph. The goal is to obtain a data structure that maintains shortest paths from $r$ to all vertices in $V$ and can answer distance queries in $O(1)$ time, as well as return the corresponding path $P$ in $O(|P|)$ time. This problem was first considered by Even and Shiloach [JACM81], who provided an algorithm with total update time $O(mn)$ for unweighted undirected graphs; this was later extended to directed weighted graphs [FOCS95, STOC99]. There are conditional lower bounds showing that $O(mn)$ is in fact near-optimal [ESA04, FOCS14, STOC15, STOC20]. In a breakthrough result, Forster et al. showed that it is possible to achieve total update time $mn^{0.9+o(1)}log W$ if the algorithm is allowed to return $(1+{epsilon})$-approximate paths, instead of exact ones [STOC14, ICALP15]. No further progress was made until Probst Gutenberg and Wulff-Nilsen [SODA20] provided a new approach for the problem, which yields total time $tilde{O}(min{m^{2/3}n^{4/3}log W, (mn)^{7/8} log W})$. Our result builds on this recent approach, but overcomes its limitations by introducing a significantly more powerful abstraction, as well as a different core subroutine. Our new framework yields a decremental $(1+{epsilon})$-approximate SSSP data structure with total update time $tilde{O}(n^2 log^4 W)$. Our algorithm is thus near-optimal for dense graphs with polynomial edge-weights. Our framework can also be applied to sparse graphs to obtain total update time $tilde{O}(mn^{2/3} log^3 W)$. Our main technique allows us to convert SSSP algorithms for DAGs to ones for general graphs, which we believe has significant potential to influence future work.
Given a dynamic digraph $G = (V,E)$ undergoing edge deletions and given $sin V$ and $epsilon>0$, we consider the problem of maintaining $(1+epsilon)$-approximate shortest path distances from $s$ to all vertices in $G$ over the sequence of deletions.
Given a weighted undirected graph $G=(V,E,w)$, a hopset $H$ of hopbound $beta$ and stretch $(1+epsilon)$ is a set of edges such that for any pair of nodes $u, v in V$, there is a path in $G cup H$ of at most $beta$ hops, whose length is within a $(1+
In the decremental single-source shortest paths problem, the goal is to maintain distances from a fixed source $s$ to every vertex $v$ in an $m$-edge graph undergoing edge deletions. In this paper, we conclude a long line of research on this problem
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
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