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