[{"title":"Distributed edge connectivity in sublinear time","date_created":"2022-08-16T09:11:17Z","article_processing_charge":"No","publication_status":"published","author":[{"full_name":"Daga, Mohit","last_name":"Daga","first_name":"Mohit"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"},{"first_name":"Thatchaphol","last_name":"Saranurak","full_name":"Saranurak, Thatchaphol"}],"scopus_import":"1","_id":"11865","publisher":"Association for Computing Machinery","quality_controlled":"1","page":"343–354","abstract":[{"lang":"eng","text":"We present the first sublinear-time algorithm that can compute the edge connectivity λ of a network exactly on distributed message-passing networks (the CONGEST model), as long as the network contains no multi-edge. We present the first sublinear-time algorithm for a distributed message-passing network sto compute its edge connectivity λ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm takes Õ(n1−1/353D1/353+n1−1/706) time to compute λ and a cut of cardinality λ with high probability, where n and D are the number of nodes and the diameter of the network, respectively, and Õ hides polylogarithmic factors. This running time is sublinear in n (i.e. Õ(n1−є)) whenever D is. Previous sublinear-time distributed algorithms can solve this problem either (i) exactly only when λ=O(n1/8−є) [Thurimella PODC’95; Pritchard, Thurimella, ACM Trans. Algorithms’11; Nanongkai, Su, DISC’14] or (ii) approximately [Ghaffari, Kuhn, DISC’13; Nanongkai, Su, DISC’14]. To achieve this we develop and combine several new techniques. First, we design the first distributed algorithm that can compute a k-edge connectivity certificate for any k=O(n1−є) in time Õ(√nk+D). The previous sublinear-time algorithm can do so only when k=o(√n) [Thurimella PODC’95]. In fact, our algorithm can be turned into the first parallel algorithm with polylogarithmic depth and near-linear work. Previous near-linear work algorithms are essentially sequential and previous polylogarithmic-depth algorithms require Ω(mk) work in the worst case (e.g. [Karger, Motwani, STOC’93]). Second, we show that by combining the recent distributed expander decomposition technique of [Chang, Pettie, Zhang, SODA’19] with techniques from the sequential deterministic edge connectivity algorithm of [Kawarabayashi, Thorup, STOC’15], we can decompose the network into a sublinear number of clusters with small average diameter and without any mincut separating a cluster (except the “trivial” ones). This leads to a simplification of the Kawarabayashi-Thorup framework (except that we are randomized while they are deterministic). This might make this framework more useful in other models of computation. Finally, by extending the tree packing technique from [Karger STOC’96], we can find the minimum cut in time proportional to the number of components. As a byproduct of this technique, we obtain an Õ(n)-time algorithm for computing exact minimum cut for weighted graphs."}],"day":"01","doi":"10.1145/3313276.3316346","arxiv":1,"external_id":{"arxiv":["1904.04341"]},"year":"2019","citation":{"mla":"Daga, Mohit, et al. “Distributed Edge Connectivity in Sublinear Time.” <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, Association for Computing Machinery, 2019, pp. 343–354, doi:<a href=\"https://doi.org/10.1145/3313276.3316346\">10.1145/3313276.3316346</a>.","short":"M. Daga, M.H. Henzinger, D. Nanongkai, T. Saranurak, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2019, pp. 343–354.","ista":"Daga M, Henzinger MH, Nanongkai D, Saranurak T. 2019. Distributed edge connectivity in sublinear time. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 343–354.","apa":"Daga, M., Henzinger, M. H., Nanongkai, D., &#38; Saranurak, T. (2019). Distributed edge connectivity in sublinear time. In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 343–354). Phoenix, AZ, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3313276.3316346\">https://doi.org/10.1145/3313276.3316346</a>","ama":"Daga M, Henzinger MH, Nanongkai D, Saranurak T. Distributed edge connectivity in sublinear time. In: <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>. Association for Computing Machinery; 2019:343–354. doi:<a href=\"https://doi.org/10.1145/3313276.3316346\">10.1145/3313276.3316346</a>","chicago":"Daga, Mohit, Monika H Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak. “Distributed Edge Connectivity in Sublinear Time.” In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, 343–354. Association for Computing Machinery, 2019. <a href=\"https://doi.org/10.1145/3313276.3316346\">https://doi.org/10.1145/3313276.3316346</a>.","ieee":"M. Daga, M. H. Henzinger, D. Nanongkai, and T. Saranurak, “Distributed edge connectivity in sublinear time,” in <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, Phoenix, AZ, United States, 2019, pp. 343–354."},"date_updated":"2023-02-17T10:26:25Z","extern":"1","month":"06","oa_version":"Preprint","publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing","conference":{"start_date":"2019-06-23","name":"STOC: Symposium on Theory of Computing","end_date":"2019-06-26","location":"Phoenix, AZ, United States"},"language":[{"iso":"eng"}],"oa":1,"publication_identifier":{"issn":["0737-8017"],"isbn":["978-1-4503-6705-9"]},"type":"conference","date_published":"2019-06-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1904.04341","open_access":"1"}]},{"extern":"1","external_id":{"arxiv":["1504.07056"]},"date_updated":"2023-02-17T10:32:23Z","citation":{"chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, 489–98. Association for Computing Machinery, 2016. <a href=\"https://doi.org/10.1145/2897518.2897638\">https://doi.org/10.1145/2897518.2897638</a>.","ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” in <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Cambridge, MA, United States, 2016, pp. 489–498.","ama":"Henzinger MH, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>. Association for Computing Machinery; 2016:489-498. doi:<a href=\"https://doi.org/10.1145/2897518.2897638\">10.1145/2897518.2897638</a>","apa":"Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2016). A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 489–498). Cambridge, MA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2897518.2897638\">https://doi.org/10.1145/2897518.2897638</a>","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2016. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 489–498.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 48th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp. 489–498.","mla":"Henzinger, Monika H., et al. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Association for Computing Machinery, 2016, pp. 489–98, doi:<a href=\"https://doi.org/10.1145/2897518.2897638\">10.1145/2897518.2897638</a>."},"year":"2016","abstract":[{"lang":"eng","text":"We present a deterministic (1+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation Õ(n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1/8, and (ii) the O(є−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s Õ(n1/2+є+D)-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω(n1/2/logn + D) [Das Sarma et al. STOC 2011] modulo some lower-order terms, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for approximating a network’s weighted diameter which almost matches the lower bound by Holzer et al. [PODC 2012].\r\n\r\nIn achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic, construction of an (no(1), o(1))-hop set of size O(n1+o(1)). We combine these techniques with many distributed algorithmic techniques, some of which from problems that are not directly related to shortest paths, e.g. ruling sets [Goldberg et al. STOC 1987], source detection [Lenzen, Peleg PODC 2013], and partial distance estimation [Lenzen, Patt-Shamir PODC 2015]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation O(no(1))-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation O(no(1)logW)-pass O(n1+o(1)logW)-space streaming algorithm, when edge weights are in {1, 2, …, W}. The first result answers an open problem in [Nanongkai, STOC 2014]. The second result partially answers an open problem raised by McGregor in 2006 [<pre>sublinear.info</pre>, Problem 14]."}],"arxiv":1,"doi":"10.1145/2897518.2897638","day":"01","page":"489 - 498","quality_controlled":"1","publisher":"Association for Computing Machinery","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Krinninger","first_name":"Sebastian","full_name":"Krinninger, Sebastian"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"}],"_id":"11866","scopus_import":"1","title":"A deterministic almost-tight distributed algorithm for approximating single-source shortest paths","publication_status":"published","article_processing_charge":"No","date_created":"2022-08-16T09:19:31Z","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://arxiv.org/abs/1504.07056","open_access":"1"}],"date_published":"2016-06-01T00:00:00Z","type":"conference","oa":1,"publication_identifier":{"issn":["0737-8017"],"isbn":["978-145034132-5"]},"language":[{"iso":"eng"}],"conference":{"name":"STOC: Symposium on Theory of Computing","start_date":"2016-06-19","location":"Cambridge, MA, United States","end_date":"2016-06-21"},"publication":"48th Annual ACM SIGACT Symposium on Theory of Computing","month":"06","oa_version":"Preprint"},{"day":"01","doi":"10.1145/2897518.2897568","arxiv":1,"abstract":[{"text":"We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2+є)-approximate maximum matching in general graphs with O(poly(logn, 1/є)) update time. (2) An algorithm that maintains an αK approximation of the value of the maximum matching with O(n2/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1≤ αK < 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(logn)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.","lang":"eng"}],"year":"2016","citation":{"chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “New Deterministic Approximation Algorithms for Fully Dynamic Matching.” In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, 398–411. Association for Computing Machinery, 2016. <a href=\"https://doi.org/10.1145/2897518.2897568\">https://doi.org/10.1145/2897518.2897568</a>.","ieee":"S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “New deterministic approximation algorithms for fully dynamic matching,” in <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Cambridge, MA, United States, 2016, pp. 398–411.","apa":"Bhattacharya, S., Henzinger, M. H., &#38; Nanongkai, D. (2016). New deterministic approximation algorithms for fully dynamic matching. In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 398–411). Cambridge, MA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2897518.2897568\">https://doi.org/10.1145/2897518.2897568</a>","ama":"Bhattacharya S, Henzinger MH, Nanongkai D. New deterministic approximation algorithms for fully dynamic matching. In: <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>. Association for Computing Machinery; 2016:398-411. doi:<a href=\"https://doi.org/10.1145/2897518.2897568\">10.1145/2897518.2897568</a>","ista":"Bhattacharya S, Henzinger MH, Nanongkai D. 2016. New deterministic approximation algorithms for fully dynamic matching. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 398–411.","mla":"Bhattacharya, Sayan, et al. “New Deterministic Approximation Algorithms for Fully Dynamic Matching.” <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Association for Computing Machinery, 2016, pp. 398–411, doi:<a href=\"https://doi.org/10.1145/2897518.2897568\">10.1145/2897518.2897568</a>.","short":"S. Bhattacharya, M.H. Henzinger, D. Nanongkai, in:, 48th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp. 398–411."},"date_updated":"2023-02-17T11:08:19Z","external_id":{"arxiv":["1604.05765"]},"extern":"1","article_processing_charge":"No","date_created":"2022-08-16T09:27:35Z","publication_status":"published","title":"New deterministic approximation algorithms for fully dynamic matching","scopus_import":"1","_id":"11867","author":[{"full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya","first_name":"Sayan"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Nanongkai","first_name":"Danupon","full_name":"Nanongkai, Danupon"}],"publisher":"Association for Computing Machinery","quality_controlled":"1","page":"398 - 411","publication_identifier":{"isbn":["978-145034132-5"],"issn":["0737-8017"]},"oa":1,"type":"conference","date_published":"2016-06-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.05765"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","month":"06","publication":"48th Annual ACM SIGACT Symposium on Theory of Computing","conference":{"start_date":"2016-06-19","name":"STOC: Symposium on Theory of Computing","location":"Cambridge, MA, United States","end_date":"2016-06-21"},"language":[{"iso":"eng"}]},{"publisher":"Association for Computing Machinery","page":"173 - 182","quality_controlled":"1","title":"Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams","publication_status":"published","article_processing_charge":"No","date_created":"2022-08-16T09:36:48Z","author":[{"full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya","first_name":"Sayan"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"},{"full_name":"Tsourakakis, Charalampos","first_name":"Charalampos","last_name":"Tsourakakis"}],"_id":"11869","scopus_import":"1","extern":"1","abstract":[{"lang":"eng","text":"While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge.\r\n\r\nGiven an input graph, the densest subgraph is the subgraph that maximizes the ratio between the number of edges and the number of nodes. For any ε>0, our algorithm can, with high probability, maintain a (4+ε)-approximate solution under edge insertions and deletions using ~O(n) space and ~O(1) amortized time per update; here, $n$ is the number of nodes in the graph and ~O hides the O(polylog_{1+ε} n) term. The approximation ratio can be improved to (2+ε) with more time. It can be extended to a (2+ε)-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in one pass. Prior to this, no algorithm could do so even in the special case of an incremental stream and even when there is no time restriction. The previously best algorithm in this setting required O(log n) passes [BahmaniKV12]. The space required by our algorithm is tight up to a polylogarithmic factor."}],"arxiv":1,"doi":"10.1145/2746539.2746592","day":"01","external_id":{"arxiv":["1504.02268"]},"date_updated":"2023-02-17T11:17:03Z","year":"2015","citation":{"ista":"Bhattacharya S, Henzinger MH, Nanongkai D, Tsourakakis C. 2015. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. 47th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 173–182.","mla":"Bhattacharya, Sayan, et al. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” <i>47th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2015, pp. 173–82, doi:<a href=\"https://doi.org/10.1145/2746539.2746592\">10.1145/2746539.2746592</a>.","short":"S. Bhattacharya, M.H. Henzinger, D. Nanongkai, C. Tsourakakis, in:, 47th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2015, pp. 173–182.","ieee":"S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and C. Tsourakakis, “Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams,” in <i>47th Annual ACM Symposium on Theory of Computing</i>, Portland, OR, United States, 2015, pp. 173–182.","chicago":"Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis. “Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.” In <i>47th Annual ACM Symposium on Theory of Computing</i>, 173–82. Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2746539.2746592\">https://doi.org/10.1145/2746539.2746592</a>.","apa":"Bhattacharya, S., Henzinger, M. H., Nanongkai, D., &#38; Tsourakakis, C. (2015). Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In <i>47th Annual ACM Symposium on Theory of Computing</i> (pp. 173–182). Portland, OR, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2746539.2746592\">https://doi.org/10.1145/2746539.2746592</a>","ama":"Bhattacharya S, Henzinger MH, Nanongkai D, Tsourakakis C. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: <i>47th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2015:173-182. doi:<a href=\"https://doi.org/10.1145/2746539.2746592\">10.1145/2746539.2746592</a>"},"conference":{"location":"Portland, OR, United States","end_date":"2015-06-17","start_date":"2015-06-14","name":"STOC: Symposium on Theory of Computing"},"language":[{"iso":"eng"}],"month":"06","oa_version":"Preprint","publication":"47th Annual ACM Symposium on Theory of Computing","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1504.02268"}],"oa":1,"publication_identifier":{"issn":["0737-8017"],"isbn":["978-145033536-2"]},"date_published":"2015-06-01T00:00:00Z","type":"conference"},{"_id":"11870","scopus_import":"1","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"}],"publication_status":"published","article_processing_charge":"No","date_created":"2022-08-16T09:41:57Z","title":"Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs","quality_controlled":"1","publisher":"Association for Computing Machinery","date_updated":"2023-02-17T11:18:52Z","citation":{"mla":"Henzinger, Monika H., et al. “Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs.” <i>46th Annual ACM Symposium on Theory of Computing</i>, 674–683, Association for Computing Machinery, 2014, doi:<a href=\"https://doi.org/10.1145/2591796.2591869\">10.1145/2591796.2591869</a>.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 46th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2014.","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2014. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. 46th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 674–683.","apa":"Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2014). Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In <i>46th Annual ACM Symposium on Theory of Computing</i>. New York, NY, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2591796.2591869\">https://doi.org/10.1145/2591796.2591869</a>","ama":"Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In: <i>46th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2014. doi:<a href=\"https://doi.org/10.1145/2591796.2591869\">10.1145/2591796.2591869</a>","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs.” In <i>46th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery, 2014. <a href=\"https://doi.org/10.1145/2591796.2591869\">https://doi.org/10.1145/2591796.2591869</a>.","ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs,” in <i>46th Annual ACM Symposium on Theory of Computing</i>, New York, NY, United States, 2014."},"year":"2014","external_id":{"arxiv":["1504.07959"]},"doi":"10.1145/2591796.2591869","arxiv":1,"day":"01","abstract":[{"lang":"eng","text":"We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach (JACM 1981); it has O(1) query time and O(mn) total update time (i.e., linear amortized update time if all edges are deleted). This algorithm serves as a building block for several other dynamic algorithms. The question whether its total update time can be improved is a major, long standing, open problem.\r\n\r\nIn this paper, we answer this question affirmatively. We obtain a randomized algorithm which, in a simplified form, achieves an Õ(mn0.984) expected total update time for SSR and (1 + ε)-approximate SSSP, where Õ(·) hides poly log n. We also extend our algorithm to achieve roughly the same running time for Strongly Connected Components (SCC), improving the algorithm of Roditty and Zwick (FOCS 2002), and an algorithm that improves the Õ (mn log W)-time algorithm of Bernstein (STOC 2013) for approximating SSSP on weighted directed graphs, where the edge weights are integers from 1 to W. All our algorithms have constant query time in the worst case."}],"extern":"1","publication":"46th Annual ACM Symposium on Theory of Computing","oa_version":"Preprint","month":"05","article_number":"674 - 683","language":[{"iso":"eng"}],"conference":{"start_date":"2014-05-31","name":"STOC: Symposium on Theory of Computing","end_date":"2014-06-03","location":"New York, NY, United States"},"date_published":"2014-05-01T00:00:00Z","type":"conference","publication_identifier":{"isbn":["978-145032710-7"],"issn":["0737-8017"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1504.07959"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public"}]