@inproceedings{11785,
  abstract     = {Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with 𝑜(𝑚𝑛) total update time, where 𝑚 is the number of edges and 𝑛 is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different 𝑚 vs. 𝑛 trade-off. For the case of 𝑚=Θ(𝑛1.5) the running time is 𝑂(𝑛2.47), just barely below 𝑚𝑛=Θ(𝑛2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of 𝑂̃ (min(𝑚7/6𝑛2/3,𝑚3/4𝑛5/4+𝑜(1),𝑚2/3𝑛4/3+𝑜(1)+𝑚3/7𝑛12/7+𝑜(1))). This gives, e.g., 𝑂(𝑛2.36) for the notorious case 𝑚=Θ(𝑛1.5). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.},
  author       = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon},
  booktitle    = {42nd International Colloquium on Automata, Languages and Programming},
  isbn         = {9783662476710},
  issn         = {0302-9743},
  location     = {Kyoto, Japan},
  pages        = {725 -- 736},
  publisher    = {Springer Nature},
  title        = {{Improved algorithms for decremental single-source reachability on directed graphs}},
  doi          = {10.1007/978-3-662-47672-7_59},
  volume       = {9134},
  year         = {2015},
}

@inproceedings{11786,
  abstract     = {In this paper, we develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an 𝑂(𝑓2)-approximately optimal solution in 𝑂(𝑓⋅log(𝑚+𝑛)) amortized update time, where 𝑓 is the maximum “frequency” of an element, 𝑛 is the number of sets, and 𝑚 is the maximum number of elements in the universe at any point in time. (2) For the dynamic 𝑏-matching problem, we maintain an 𝑂(1)-approximately optimal solution in 𝑂(log3𝑛) amortized update time, where 𝑛 is the number of nodes in the graph.},
  author       = {Bhattacharya, Sayan and Henzinger, Monika H and Italiano, Giuseppe F.},
  booktitle    = {42nd International Colloquium on Automata, Languages and Programming},
  isbn         = {9783662476710},
  issn         = {0302-9743},
  location     = {Kyoto, Japan},
  pages        = {206 -- 218},
  publisher    = {Springer Nature},
  title        = {{Design of dynamic algorithms via primal-dual method}},
  doi          = {10.1007/978-3-662-47672-7_17},
  volume       = {9134},
  year         = {2015},
}

@inproceedings{11787,
  abstract     = {We present faster algorithms for computing the 2-edge and 2-vertex strongly connected components of a directed graph. While in undirected graphs the 2-edge and 2-vertex connected components can be found in linear time, in directed graphs with m edges and n vertices only rather simple O(m n)-time algorithms were known. We use a hierarchical sparsification technique to obtain algorithms that run in time 𝑂(𝑛2). For 2-edge strongly connected components our algorithm gives the first running time improvement in 20 years. Additionally we present an 𝑂(𝑚2/log𝑛)-time algorithm for 2-edge strongly connected components, and thus improve over the O(m n) running time also when 𝑚=𝑂(𝑛). Our approach extends to k-edge and k-vertex strongly connected components for any constant k with a running time of 𝑂(𝑛2log𝑛) for k-edge-connectivity and 𝑂(𝑛3) for k-vertex-connectivity.},
  author       = {Henzinger, Monika H and Krinninger, Sebastian and Loitzenbauer, Veronika},
  booktitle    = {2nd International Colloquium on Automata, Languages and Programming},
  isbn         = {9783662476710},
  issn         = {0302-9743},
  location     = {Kyoto, Japan},
  pages        = {713 -- 724},
  publisher    = {Springer Nature},
  title        = {{Finding 2-edge and 2-vertex strongly connected components in quadratic time}},
  doi          = {10.1007/978-3-662-47672-7_58},
  volume       = {9134},
  year         = {2015},
}