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