{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:17Z","timestamp":1740109277773,"version":"3.37.3"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004206","name":"Osaka University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004206","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The <jats:italic>f<\/jats:italic>-<jats:italic>fault-tolerant connectivity labeling<\/jats:italic> (<jats:italic>f<\/jats:italic>-FTC labeling) is a scheme of assigning each vertex and edge with a small-size label such that one can determine the connectivity of two vertices <jats:italic>s<\/jats:italic> and <jats:italic>t<\/jats:italic> under the presence of at most <jats:italic>f<\/jats:italic> faulty edges only from the labels of <jats:italic>s<\/jats:italic>, <jats:italic>t<\/jats:italic>, and the faulty edges. This paper presents a new deterministic <jats:italic>f<\/jats:italic>-FTC labeling scheme attaining <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(f^2 \\textrm{polylog}(n))$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mtext>polylog<\/mml:mtext>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-bit label size and a polynomial construction time, which settles the open problem left by Dory and Parter (in: Proceedings of the 2021 ACM symposium on principles of distributed computing (PODC), pp 445\u2013455, 2021). The key ingredient of our construction is to develop a deterministic counterpart of the graph sketch technique by Ahn et al. (in: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems (PODS), pp 5\u201314, 2012), via some natural connection with the theory of error-correcting codes. This technique removes one major obstacle in de-randomizing the Dory\u2013Parter scheme. The whole scheme is obtained by combining this technique with a new deterministic graph sparsification algorithm derived from the seminal <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\epsilon $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03f5<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-<jats:italic>net<\/jats:italic> theory, which is also of independent interest. As byproducts, our result deduces the first deterministic fault-tolerant approximate distance labeling scheme with a non-trivial performance guarantee and an improved deterministic fault-tolerant compact routing. The authors believe that our new technique is potentially useful in the future exploration of more efficient FTC labeling schemes and other related applications based on graph sketches.<\/jats:p>","DOI":"10.1007\/s00446-024-00472-6","type":"journal-article","created":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T19:04:00Z","timestamp":1730747040000},"page":"31-50","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic fault-tolerant connectivity labeling scheme"],"prefix":"10.1007","volume":"38","author":[{"given":"Taisuke","family":"Izumi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Emek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tadashi","family":"Wadayama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshimitsu","family":"Masuzawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,4]]},"reference":[{"key":"472_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Chechik, S., Gavoille, C.: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 1199\u20131218 (2012)","DOI":"10.1145\/2213977.2214084"},{"issue":"2","key":"472_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2818694","volume":"12","author":"I Abraham","year":"2016","unstructured":"Abraham, I., Chechik, S., Gavoille, C., Peleg, D.: Forbidden-set distance labels for graphs of bounded doubling dimension. ACM Trans. Algorithms 12(2), 1\u201317 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"472_CR3","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 459\u2013467. SIAM (2012)","DOI":"10.1137\/1.9781611973099.40"},{"key":"472_CR4","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pp. 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"472_CR5","unstructured":"Bil\u00f2, D., Choudhary, K., Gual\u00e0, L., Leucci, S., Parter, M., Proietti, G.: Efficient oracles and routing schemes for replacement paths. In: Proceedings of 35th Symposium on Theoretical Aspects of Computer Science (STACS), volume\u00a096 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 13:1\u201313:15 (2018)"},{"key":"472_CR6","doi-asserted-by":"crossref","unstructured":"Bar-Natan, A., Charalampopoulos, P., Gawrychowski, P., Mozes, S., Weimann, O.: Fault-tolerant distance labeling for planar graphs. In: Proceedings of International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 12810 of Lecture Notes in Computer Science, pp. 315\u2013333 (2021)","DOI":"10.1007\/978-3-030-79527-6_18"},{"key":"472_CR7","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Compact and fast sensitivity oracles for single-source distances. In: Sankowski, P., Zaroliagis, C.D. (eds.) Proceedings of 24th Annual European Symposium on Algorithms (ESA), volume\u00a057 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 13:1\u201313:14 (2016)"},{"key":"472_CR8","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Karger, D.: A nearly optimal oracle for avoiding failed vertices and edges. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 101\u2013110 (2009)","DOI":"10.1145\/1536414.1536431"},{"issue":"1","key":"472_CR9","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/s00453-012-9621-y","volume":"66","author":"S Baswana","year":"2013","unstructured":"Baswana, S., Khanna, N.: Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs. Algorithmica 66(1), 18\u201350 (2013)","journal-title":"Algorithmica"},{"key":"472_CR10","doi-asserted-by":"crossref","unstructured":"Chechik, S., Cohen, S., Fiat, A., Kaplan, H.: $$(1+\\epsilon )$$-Approximate $$f$$-sensitive distance oracles. In: Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1479\u20131496 (2017)","DOI":"10.1137\/1.9781611974782.96"},{"key":"472_CR11","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Gao, Y., Li, J., Nanongkai, D., Peng, R., Saranurak, T.: A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In: 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1158\u20131167. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00111"},{"key":"472_CR12","doi-asserted-by":"crossref","unstructured":"Chechik, S.: Fault-tolerant compact routing schemes for general graphs. In: 38th International Colloquium on Automata, Languages, and Programming, (ICALP), pp. 101\u2013112 (2011)","DOI":"10.1007\/978-3-642-22012-8_7"},{"issue":"4","key":"472_CR13","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1007\/s00453-011-9543-0","volume":"63","author":"S Chechik","year":"2012","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: $$f$$-sensitivity distance oracles and routing schemes. Algorithmica 63(4), 861\u2013882 (2012)","journal-title":"Algorithmica"},{"issue":"3","key":"472_CR14","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jagm.1996.0060","volume":"21","author":"B Chazelle","year":"1996","unstructured":"Chazelle, B., Matou\u0161ek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21(3), 579\u2013597 (1996)","journal-title":"J. Algorithms"},{"key":"472_CR15","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Twigg, A.: Compact forbidden-set routing. In: Proceedings of the 24th Annual Conference on Theoretical Aspects of Computer Science, STACS\u201907, pp. 37\u201348 (2007)","DOI":"10.1007\/978-3-540-70918-3_4"},{"issue":"2","key":"472_CR16","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s00224-009-9211-9","volume":"47","author":"B Courcelle","year":"2010","unstructured":"Courcelle, B., Twigg, A.: Constrained-path labellings on graphs of bounded clique-width. Theory Comput. Syst. 47(2), 531\u2013567 (2010)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"472_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/060651380","volume":"38","author":"Y Dodis","year":"2008","unstructured":"Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97\u2013139 (2008)","journal-title":"SIAM J. Comput."},{"key":"472_CR18","doi-asserted-by":"crossref","unstructured":"Duan, R, Pettie, S: Dual-failure distance and connectivity oracles. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 506\u2013515 (2009)","DOI":"10.1137\/1.9781611973068.56"},{"key":"472_CR19","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Connectivity oracles for failure prone graphs. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pp. 465\u2013474 (2010)","DOI":"10.1145\/1806689.1806754"},{"issue":"6","key":"472_CR20","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1137\/17M1146610","volume":"49","author":"R Duan","year":"2020","unstructured":"Duan, R., Pettie, S.: Connectivity oracles for graphs subject to vertex failures. SIAM J. Comput. 49(6), 1363\u20131396 (2020)","journal-title":"SIAM J. Comput."},{"key":"472_CR21","doi-asserted-by":"crossref","unstructured":"Dory, M., Parter, M.: Fault-tolerant labeling and compact routing schemes. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC), pp. 445\u2013455 (2021)","DOI":"10.1145\/3465084.3467929"},{"key":"472_CR22","unstructured":"Demetrescu, C., Thorup, M.: Oracles for distances avoiding a link-failure. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 838\u2013843 (2002)"},{"issue":"2","key":"472_CR23","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.tcs.2007.02.020","volume":"378","author":"J Feigenbaum","year":"2007","unstructured":"Feigenbaum, J., Karger, D.R., Mirrokni, V.S., Sami, R.: Subjective-cost policy routing. Theor. Comput. Sci. 378(2), 175\u2013189 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"472_CR24","unstructured":"Ghaffari, M., Kuhn, F.: Distributed MST and broadcast with fewer messages, and faster gossiping. In: Proceedings of 32nd International Symposium on Distributed Computing (DISC), volume 121 of LIPIcs, pp. 30:1\u201330:12 (2018)"},{"key":"472_CR25","unstructured":"Gibb, D., Kapron, B.M., King, V., Thorn, N.: Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR, arXiv:1509.06464 (2015)"},{"key":"472_CR26","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Parter, M.: Mst in log-star rounds of congested clique. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pp. 19\u201328 (2016)","DOI":"10.1145\/2933057.2933103"},{"key":"472_CR27","unstructured":"Gmyr, R., Pandurangan, G.: Time-message trade-offs in distributed algorithms. In: Proceedings of 32nd International Symposium on Distributed Computing (DISC), volume 121 of LIPIcs, pp. 32:1\u201332:18 (2018)"},{"key":"472_CR28","unstructured":"Gu, Y., Ren, H.: Constructing a distance sensitivity oracle in $$o(n^{2.5794}m)$$ time. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 198 of LIPIcs, pp. 76:1\u201376:20 (2021)"},{"issue":"1","key":"472_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3365835","volume":"16","author":"F Grandoni","year":"2019","unstructured":"Grandoni, F., Williams, V.V.: Faster replacement paths and distance sensitivity oracles. ACM Trans. Algorithms 16(1), 1\u201325 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"472_CR30","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"472_CR31","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"MR Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4), 502\u2013516 (1999)","journal-title":"J. ACM"},{"key":"472_CR32","doi-asserted-by":"crossref","unstructured":"Hegeman, J.W., Pandurangan, G., Pemmaraju, S.V., Sardeshmukh, V.B., Scquizzato, M.: Toward optimal bounds in the congested clique: graph connectivity and mst. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), pp. 91\u2013100 (2015)","DOI":"10.1145\/2767386.2767434"},{"key":"472_CR33","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"472_CR34","doi-asserted-by":"crossref","unstructured":"Jurdzinski, T., Nowicki, K.: MST in $$O(1)$$ rounds of the congested clique. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2620\u20132632 (2018)","DOI":"10.1137\/1.9781611975031.167"},{"key":"472_CR35","unstructured":"Kulkarni, J., Govindarajan, S.: New epsilon-net constructions. In: 22nd Annual Canadian Conference on Computational Geometry (CCCG), pp. 159\u2013162 (2010)"},{"key":"472_CR36","doi-asserted-by":"crossref","unstructured":"Kapron, B.M., King, V., Mountjoy, B.: Dynamic graph connectivity in polylogarithmic worst case time. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1131\u20131142 (2013)","DOI":"10.1137\/1.9781611973105.81"},{"key":"472_CR37","doi-asserted-by":"crossref","unstructured":"King, V., Kutten, S., Thorup, M.: Construction and impromptu repair of an mst in a distributed network with $$o(m)$$ communication. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 71\u201380 (2015)","DOI":"10.1145\/2767386.2767405"},{"key":"472_CR38","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Lee, Y.T., Musco, C., Musco, C., Sidford, A.: Single pass spectral sparsification in dynamic streams. In: Proceedings of 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 561\u2013570 (2014)","DOI":"10.1109\/FOCS.2014.66"},{"issue":"4","key":"472_CR39","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5(4), 596\u2013603 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"472_CR40","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Woodruff, D.: Spanners and sparsifiers in dynamic streams. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC), pp. 272\u2013281 (2014)","DOI":"10.1145\/2611462.2611497"},{"issue":"3","key":"472_CR41","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1006\/jagm.1996.0027","volume":"20","author":"J Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J.: Derandomization in computational geometry. J. Algorithms 20(3), 545\u2013580 (1996)","journal-title":"J. Algorithms"},{"issue":"5","key":"472_CR42","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1007\/s00493-017-3564-5","volume":"38","author":"NH Mustafa","year":"2018","unstructured":"Mustafa, N.H., Dutta, K., Ghosh, A.: A simple proof of optimal epsilon nets. Combinatorica 38(5), 1269\u20131277 (2018)","journal-title":"Combinatorica"},{"issue":"4","key":"472_CR43","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s00446-020-00387-y","volume":"34","author":"A Mashreghi","year":"2021","unstructured":"Mashreghi, A., King, V.: Broadcast and minimum spanning tree with $$o(m)$$ messages in the asynchronous CONGEST model. Distrib. Comput. 34(4), 283\u2013299 (2021)","journal-title":"Distrib. Comput."},{"issue":"4","key":"472_CR44","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M Patrascu","year":"2006","unstructured":"Patrascu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35(4), 932\u2013963 (2006)","journal-title":"SIAM J. Comput."},{"key":"472_CR45","unstructured":"Parter, M., Petruschka, A.: Near-optimal distributed computation of small vertex cuts. In: 36th International Symposium on Distributed Computing (DISC), vol. 246, pp. 31:1\u201331:21 (2022)"},{"key":"472_CR46","unstructured":"Parter, M., Petruschka, A.: \u00d5ptimal dual vertex failure connectivity labels. In: 36th International Symposium on Distributed Computing (DISC 2022), pp. 32:1\u201332:19 (2022)"},{"key":"472_CR47","doi-asserted-by":"crossref","unstructured":"Parter, M., Petruschka, A., Pettie, S.: Connectivity labeling and routing with multiple vertex failures. In: 56th Annual ACM Symposium on Theory of Computing (STOC), pp. 823\u2013834 (2024)","DOI":"10.1145\/3618260.3649729"},{"key":"472_CR48","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Thorup, M.: Planning for fast connectivity updates. In: Proceedings of 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 263\u2013271 (2007)","DOI":"10.1109\/FOCS.2007.59"},{"issue":"4","key":"472_CR49","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2000807.2000814","volume":"7","author":"D Pritchard","year":"2011","unstructured":"Pritchard, D., Thurimella, R.: Fast computation of small cuts via cycle space sampling. ACM Trans. Algorithms 7(4), 1\u201330 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"472_CR50","unstructured":"Rajan, V.: Space efficient edge-fault tolerant routing. In: D\u2019Souza, D., Kavitha, T., Radhakrishnan, J. (eds.) Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, (FSTTCS), volume\u00a018 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 350\u2013361 (2012)"},{"key":"472_CR51","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: The 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 343\u2013350 (2000)","DOI":"10.1145\/335305.335345"},{"key":"472_CR52","doi-asserted-by":"crossref","unstructured":"Wulff-Nilsen, C.: Faster deterministic fully-dynamic graph connectivity. In: The 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1757\u20131769","DOI":"10.1137\/1.9781611973105.126"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-024-00472-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-024-00472-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-024-00472-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T11:39:44Z","timestamp":1739533184000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-024-00472-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["472"],"URL":"https:\/\/doi.org\/10.1007\/s00446-024-00472-6","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2024,11,4]]},"assertion":[{"value":"16 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}