[{"oa_version":"Preprint","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9783662476710"],"issn":["0302-9743"]},"extern":"1","_id":"11785","article_processing_charge":"No","date_updated":"2023-02-10T09:10:26Z","volume":9134,"oa":1,"arxiv":1,"author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"first_name":"Sebastian","full_name":"Krinninger, Sebastian","last_name":"Krinninger"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"}],"abstract":[{"text":"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.","lang":"eng"}],"citation":{"mla":"Henzinger, Monika H., et al. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” <i>42nd International Colloquium on Automata, Languages and Programming</i>, vol. 9134, Springer Nature, 2015, pp. 725–36, doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_59\">10.1007/978-3-662-47672-7_59</a>.","ama":"Henzinger MH, Krinninger S, Nanongkai D. Improved algorithms for decremental single-source reachability on directed graphs. In: <i>42nd International Colloquium on Automata, Languages and Programming</i>. Vol 9134. Springer Nature; 2015:725-736. doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_59\">10.1007/978-3-662-47672-7_59</a>","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2015. Improved algorithms for decremental single-source reachability on directed graphs. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 725–736.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 725–736.","ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Improved algorithms for decremental single-source reachability on directed graphs,” in <i>42nd International Colloquium on Automata, Languages and Programming</i>, Kyoto, Japan, 2015, vol. 9134, pp. 725–736.","apa":"Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2015). Improved algorithms for decremental single-source reachability on directed graphs. In <i>42nd International Colloquium on Automata, Languages and Programming</i> (Vol. 9134, pp. 725–736). Kyoto, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_59\">https://doi.org/10.1007/978-3-662-47672-7_59</a>","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.” In <i>42nd International Colloquium on Automata, Languages and Programming</i>, 9134:725–36. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_59\">https://doi.org/10.1007/978-3-662-47672-7_59</a>."},"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1612.03856"}],"alternative_title":["LNCS"],"title":"Improved algorithms for decremental single-source reachability on directed graphs","external_id":{"arxiv":["1612.03856"]},"year":"2015","doi":"10.1007/978-3-662-47672-7_59","page":"725 - 736","publication":"42nd International Colloquium on Automata, Languages and Programming","status":"public","intvolume":"      9134","type":"conference","day":"01","date_created":"2022-08-11T08:51:32Z","conference":{"end_date":"2015-07-10","location":"Kyoto, Japan","name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"2015-07-06"},"language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Springer Nature","date_published":"2015-01-01T00:00:00Z","month":"01"},{"citation":{"short":"S. Bhattacharya, M.H. Henzinger, G.F. Italiano, in:, 42nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 206–218.","ista":"Bhattacharya S, Henzinger MH, Italiano GF. 2015. Design of dynamic algorithms via primal-dual method. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 206–218.","ama":"Bhattacharya S, Henzinger MH, Italiano GF. Design of dynamic algorithms via primal-dual method. In: <i>42nd International Colloquium on Automata, Languages and Programming</i>. Vol 9134. Springer Nature; 2015:206-218. doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_17\">10.1007/978-3-662-47672-7_17</a>","mla":"Bhattacharya, Sayan, et al. “Design of Dynamic Algorithms via Primal-Dual Method.” <i>42nd International Colloquium on Automata, Languages and Programming</i>, vol. 9134, Springer Nature, 2015, pp. 206–18, doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_17\">10.1007/978-3-662-47672-7_17</a>.","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Design of Dynamic Algorithms via Primal-Dual Method.” In <i>42nd International Colloquium on Automata, Languages and Programming</i>, 9134:206–18. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_17\">https://doi.org/10.1007/978-3-662-47672-7_17</a>.","ieee":"S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Design of dynamic algorithms via primal-dual method,” in <i>42nd International Colloquium on Automata, Languages and Programming</i>, Kyoto, Japan, 2015, vol. 9134, pp. 206–218.","apa":"Bhattacharya, S., Henzinger, M. H., &#38; Italiano, G. F. (2015). Design of dynamic algorithms via primal-dual method. In <i>42nd International Colloquium on Automata, Languages and Programming</i> (Vol. 9134, pp. 206–218). Kyoto, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_17\">https://doi.org/10.1007/978-3-662-47672-7_17</a>"},"publication_status":"published","abstract":[{"text":"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.","lang":"eng"}],"author":[{"first_name":"Sayan","full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"full_name":"Italiano, Giuseppe F.","last_name":"Italiano","first_name":"Giuseppe F."}],"arxiv":1,"article_processing_charge":"No","volume":9134,"oa":1,"date_updated":"2023-02-10T09:13:31Z","publication_identifier":{"isbn":["9783662476710"],"issn":["0302-9743"]},"extern":"1","_id":"11786","quality_controlled":"1","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.1007/978-3-662-47672-7_17","year":"2015","title":"Design of dynamic algorithms via primal-dual method","external_id":{"arxiv":["1604.05337"]},"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.05337"}],"day":"01","type":"conference","intvolume":"      9134","status":"public","publication":"42nd International Colloquium on Automata, Languages and Programming","page":"206 - 218","month":"01","date_published":"2015-01-01T00:00:00Z","scopus_import":"1","publisher":"Springer Nature","language":[{"iso":"eng"}],"conference":{"location":"Kyoto, Japan","end_date":"2015-07-10","name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"2015-07-06"},"date_created":"2022-08-11T09:28:49Z"},{"external_id":{"arxiv":["1412.6466"]},"title":"Finding 2-edge and 2-vertex strongly connected components in quadratic time","year":"2015","doi":"10.1007/978-3-662-47672-7_58","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1412.6466"}],"alternative_title":["LNCS"],"author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"full_name":"Krinninger, Sebastian","last_name":"Krinninger","first_name":"Sebastian"},{"first_name":"Veronika","last_name":"Loitzenbauer","full_name":"Loitzenbauer, Veronika"}],"abstract":[{"text":"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.","lang":"eng"}],"publication_status":"published","citation":{"apa":"Henzinger, M. H., Krinninger, S., &#38; Loitzenbauer, V. (2015). Finding 2-edge and 2-vertex strongly connected components in quadratic time. In <i>2nd International Colloquium on Automata, Languages and Programming</i> (Vol. 9134, pp. 713–724). Kyoto, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_58\">https://doi.org/10.1007/978-3-662-47672-7_58</a>","ieee":"M. H. Henzinger, S. Krinninger, and V. Loitzenbauer, “Finding 2-edge and 2-vertex strongly connected components in quadratic time,” in <i>2nd International Colloquium on Automata, Languages and Programming</i>, Kyoto, Japan, 2015, vol. 9134, pp. 713–724.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Veronika Loitzenbauer. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” In <i>2nd International Colloquium on Automata, Languages and Programming</i>, 9134:713–24. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_58\">https://doi.org/10.1007/978-3-662-47672-7_58</a>.","mla":"Henzinger, Monika H., et al. “Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.” <i>2nd International Colloquium on Automata, Languages and Programming</i>, vol. 9134, Springer Nature, 2015, pp. 713–24, doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_58\">10.1007/978-3-662-47672-7_58</a>.","ama":"Henzinger MH, Krinninger S, Loitzenbauer V. Finding 2-edge and 2-vertex strongly connected components in quadratic time. In: <i>2nd International Colloquium on Automata, Languages and Programming</i>. Vol 9134. Springer Nature; 2015:713-724. doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_58\">10.1007/978-3-662-47672-7_58</a>","short":"M.H. Henzinger, S. Krinninger, V. Loitzenbauer, in:, 2nd International Colloquium on Automata, Languages and Programming, Springer Nature, 2015, pp. 713–724.","ista":"Henzinger MH, Krinninger S, Loitzenbauer V. 2015. Finding 2-edge and 2-vertex strongly connected components in quadratic time. 2nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 713–724."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","oa_version":"Preprint","_id":"11787","extern":"1","publication_identifier":{"isbn":["9783662476710"],"issn":["0302-9743"]},"date_updated":"2023-02-10T09:21:47Z","oa":1,"volume":9134,"article_processing_charge":"No","arxiv":1,"language":[{"iso":"eng"}],"publisher":"Springer Nature","scopus_import":"1","date_published":"2015-07-06T00:00:00Z","month":"07","date_created":"2022-08-11T09:38:34Z","conference":{"location":"Kyoto, Japan","name":"ICALP: International Colloquium on Automata, Languages, and Programming","end_date":"2015-07-10","start_date":"2015-07-06"},"status":"public","intvolume":"      9134","type":"conference","day":"06","page":"713 - 724","publication":"2nd International Colloquium on Automata, Languages and Programming"}]