@article{11768,
  abstract     = {In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+ϵ)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary.

In contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12] in the PRAM literature. An (h, ϵ)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated by their h-hop distance (given by a path containing at most h edges) on G′=(V, E ∪ F). Our algorithm can maintain an (no(1), ϵ)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest.},
  author       = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon},
  issn         = {1557-735X},
  journal      = {Journal of the ACM},
  number       = {6},
  pages        = {1--40},
  publisher    = {Association for Computing Machinery},
  title        = {{Decremental single-source shortest paths on undirected graphs in near-linear total update time}},
  doi          = {10.1145/3218657},
  volume       = {65},
  year         = {2018},
}

@article{11769,
  abstract     = {This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor.
Let n denote the number of nodes in the graph. For a sequence of Ω(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is O(p log3 n) (througout the paper the logarithms are based 2) for connectivity and bipartiteness. The worst-case time for one query is O(log n/log log n). For the k-edge witness problem (“Does the removal of k given edges disconnect the graph?”) the expected time for p updates is O(p log3 n) and the expected time for q queries is O(qk log3 n). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O(pk log3 n). This implies an algorithm to maintain a 1 + ε-approximation of the minimum spanning tree in expected time O((p log3 n logU)/ε) for p updates, where the weights of the edges are between 1 and U.},
  author       = {Henzinger, Monika H and King, Valerie},
  issn         = {1557-735X},
  journal      = {Journal of the ACM},
  number       = {4},
  pages        = {502--516},
  publisher    = {Association for Computing Machinery},
  title        = {{Randomized fully dynamic graph algorithms with polylogarithmic time per operation}},
  doi          = {10.1145/320211.320215},
  volume       = {46},
  year         = {1999},
}

@article{4046,
  abstract     = {The main contribution of this work is an O(n log n + k)-time algorithm for computing all k intersections among n line segments in the plane. This time complexity is easily shown to be optimal. Within the same asymptotic cost, our algorithm can also construct the subdivision of the plane defined by the segments and compute which segment (if any) lies right above (or below) each intersection and each endpoint. The algorithm has been implemented and performs very well. The storage requirement is on the order of n + k in the worst case, but it is considerably lower in practice. To analyze the complexity of the algorithm, an amortization argument based on a new combinatorial theorem on line arrangements is used.},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert},
  issn         = {1557-735X},
  journal      = {Journal of the ACM},
  number       = {1},
  pages        = {1 -- 54},
  publisher    = {ACM},
  title        = {{An optimal algorithm for intersecting line segments in the plane}},
  doi          = {10.1145/147508.147511},
  volume       = {39},
  year         = {1992},
}