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