{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:09Z","timestamp":1740109329265,"version":"3.37.3"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T00:00:00Z","timestamp":1718755200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T00:00:00Z","timestamp":1718755200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["OCENW.KLEIN.114"],"award-info":[{"award-number":["OCENW.KLEIN.114"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,9]]},"abstract":"Abstract<\/jats:title>We initiate the investigation of the parameterized complexity of Diameter<\/jats:sc> and Connectivity<\/jats:sc> in the streaming paradigm. On the positive end, we show that knowing a vertex cover of size k<\/jats:italic> allows for algorithms in the Adjacency List (AL) streaming model whose number of passes is constant and memory is $$\\mathcal {O}(\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any fixed k<\/jats:italic>. Underlying these algorithms is a method to execute a breadth-first search in $$\\mathcal {O}(k)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> passes and $$\\mathcal {O}(k \\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bits of memory. On the negative end, we show that many other parameters lead to lower bounds in the AL model, where $$\\Omega (n\/p)$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \/<\/mml:mo>\n p<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bits of memory is needed for any p<\/jats:italic>-pass algorithm even for constant parameter values. In particular, this holds for graphs with a known modulator (deletion set) of constant size to a graph that has no induced subgraph isomorphic to a fixed graph H<\/jats:italic>, for most H<\/jats:italic>. For some cases, we can also show one-pass, $$\\Omega (n \\log n)$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bits of memory lower bounds. We also prove a much stronger $$\\Omega (n^2\/p)$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \/<\/mml:mo>\n p<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> lower bound for Diameter<\/jats:sc> on bipartite graphs. Finally, using the insights we developed into streaming parameterized graph exploration algorithms, we show a new streaming kernelization algorithm for computing a vertex cover of size k<\/jats:italic>. This yields a kernel of 2k<\/jats:italic> vertices (with $$\\mathcal {O}(k^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> edges) produced as a stream in $$\\text {poly}(k)$$<\/jats:tex-math>\n \n poly<\/mml:mtext>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> passes and only $$\\mathcal {O}(k \\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bits of memory.<\/jats:p>","DOI":"10.1007\/s00453-024-01246-z","type":"journal-article","created":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T11:01:52Z","timestamp":1718794912000},"page":"2885-2928","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of Streaming Diameter and Connectivity Problems"],"prefix":"10.1007","volume":"86","author":[{"given":"Jelle J.","family":"Oostveen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,19]]},"reference":[{"key":"1246_CR1","doi-asserted-by":"publisher","unstructured":"Oostveen, J.J., van Leeuwen, E.J.: Parameterized complexity of streaming diameter and connectivity problems. In: Dell, H., Nederlof, J. (eds.) 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7\u20139, 2022, Potsdam, Germany. LIPIcs, vol. 249, pp. 24\u201312416. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2022). https:\/\/doi.org\/10.4230\/LIPICS.IPEC.2022.24","DOI":"10.4230\/LIPICS.IPEC.2022.24"},{"key":"1246_CR2","doi-asserted-by":"publisher","unstructured":"Henzinger, M.R., Raghavan, P., Rajagopalan, S.: Computing on data streams. In: Abello, J.M., Vitter, J.S. (eds.) External Memory Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, May 20\u201322, 1998. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 50, pp. 107\u2013118. DIMACS\/AMS, Providence (1998). https:\/\/doi.org\/10.1090\/dimacs\/050\/05","DOI":"10.1090\/dimacs\/050\/05"},{"issue":"2\u20133","key":"1246_CR3","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theor. Comput. Sci. 348(2\u20133), 207\u2013216 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.09.013","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1246_CR4","doi-asserted-by":"publisher","first-page":"1709","DOI":"10.1137\/070683155","volume":"38","author":"J Feigenbaum","year":"2008","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the data-stream model. SIAM J. Comput. 38(5), 1709\u20131727 (2008). https:\/\/doi.org\/10.1137\/070683155","journal-title":"SIAM J. Comput."},{"key":"1246_CR5","doi-asserted-by":"publisher","unstructured":"Sun, X., Woodruff, D.P.: Tight bounds for graph problems in insertion streams. In: Garg, N., Jansen, K., Rao, A., Rolim, J.D.P. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2015, August 24\u201326, 2015, Princeton, NJ, USA. LIPIcs, vol. 40, pp. 435\u2013448. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2015). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2015.435","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.435"},{"issue":"1","key":"1246_CR6","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph stream algorithms: a survey. SIGMOD Rec. 43(1), 9\u201320 (2014). https:\/\/doi.org\/10.1145\/2627692.2627694","journal-title":"SIGMOD Rec."},{"key":"1246_CR7","doi-asserted-by":"publisher","unstructured":"Khan, S., Mehta, S.K.: Depth first search in the semi-streaming model. In: Niedermeier, R., Paul, C. (eds.) 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13\u201316, 2019, Berlin, Germany. LIPIcs, vol. 126, pp. 42\u201314216. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.42","DOI":"10.4230\/LIPIcs.STACS.2019.42"},{"issue":"3","key":"1246_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/3387161","volume":"67","author":"M Elkin","year":"2020","unstructured":"Elkin, M.: Distributed exact shortest paths in sublinear time. J. ACM 67(3), 15\u201311536 (2020). https:\/\/doi.org\/10.1145\/3387161","journal-title":"J. ACM"},{"key":"1246_CR9","doi-asserted-by":"publisher","unstructured":"Elkin, M., Trehan, C.: (1+$$\\epsilon $$)-approximate shortest paths in dynamic streams. In: Chakrabarti, A., Swamy, C. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2022, September 19\u201321, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference). LIPIcs, vol. 245, pp. 51\u201315123. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2022). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2022.51","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2022.51"},{"issue":"5","key":"1246_CR10","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"JH Reif","year":"1985","unstructured":"Reif, J.H.: Depth-first search is inherently sequential. Inf. Process. Lett. 20(5), 229\u2013234 (1985). https:\/\/doi.org\/10.1016\/0020-0190(85)90024-9","journal-title":"Inf. Process. Lett."},{"key":"1246_CR11","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science, Springer, New York (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9"},{"key":"1246_CR12","doi-asserted-by":"publisher","unstructured":"Fafianie, S., Kratsch, S.: Streaming kernelization. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) Mathematical Foundations of Computer Science 2014\u201439th International Symposium, MFCS 2014, Budapest, Hungary, August 25\u201329, 2014. Proceedings, Part II. Lecture Notes in Computer Science, vol. 8635, pp. 275\u2013286. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44465-8_24","DOI":"10.1007\/978-3-662-44465-8_24"},{"key":"1246_CR13","doi-asserted-by":"publisher","unstructured":"Chitnis, R.H., Cormode, G., Hajiaghayi, M.T., Monemizadeh, M.: Parameterized streaming: maximal matching and vertex cover. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015, pp. 1234\u20131251. SIAM, Philadelphia (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.82","DOI":"10.1137\/1.9781611973730.82"},{"key":"1246_CR14","doi-asserted-by":"publisher","unstructured":"Chitnis, R., Cormode, G.: Towards a theory of parameterized streaming algorithms. In: Jansen, B.M.P., Telle, J.A. (eds.) 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11\u201313, 2019, Munich, Germany. LIPIcs, vol. 148, pp. 7\u20131715. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2019). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2019.7","DOI":"10.4230\/LIPIcs.IPEC.2019.7"},{"key":"1246_CR15","doi-asserted-by":"publisher","unstructured":"Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 1326\u20131344. SIAM, Philadelphia (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch92","DOI":"10.1137\/1.9781611974331.ch92"},{"key":"1246_CR16","doi-asserted-by":"publisher","unstructured":"Bishnu, A., Ghosh, A., Kolay, S., Mishra, G., Saurabh, S.: Fixed parameter tractability of graph deletion problems over data streams. In: Kim, D., Uma, R.N., Cai, Z., Lee, D.H. (eds.) Computing and Combinatorics\u201426th International Conference, COCOON 2020, Atlanta, GA, USA, August 29\u201331, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12273, pp. 652\u2013663. Springer, Heidelberg (2020). https:\/\/doi.org\/10.1007\/978-3-030-58150-3_53","DOI":"10.1007\/978-3-030-58150-3_53"},{"key":"1246_CR17","doi-asserted-by":"publisher","unstructured":"Oostveen, J.J., van Leeuwen, E.J.: Streaming deletion problems parameterized by vertex cover. In: Bampis, E., Pagourtzis, A. (eds.) Fundamentals of Computation Theory\u201423rd International Symposium, FCT 2021, Athens, Greece, September 12\u201315, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12867, pp. 413\u2013426. Springer, Heidelberg (2021). https:\/\/doi.org\/10.1007\/978-3-030-86593-1_29","DOI":"10.1007\/978-3-030-86593-1_29"},{"key":"1246_CR18","doi-asserted-by":"publisher","unstructured":"Goel, A., Kapralov, M., Khanna, S.: On the communication and streaming complexity of maximum bipartite matching. In: Rabani, Y. (ed.) Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17\u201319, 2012, pp. 468\u2013485. SIAM, Philadelphia (2012). https:\/\/doi.org\/10.1137\/1.9781611973099.41","DOI":"10.1137\/1.9781611973099.41"},{"key":"1246_CR19","doi-asserted-by":"publisher","unstructured":"Kapralov, M.: Better bounds for matchings in the streaming model. In: Khanna, S. (ed.) Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6\u20138, 2013, pp. 1679\u20131697. SIAM, Philadelphia (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.121","DOI":"10.1137\/1.9781611973105.121"},{"key":"1246_CR20","doi-asserted-by":"publisher","unstructured":"McGregor, A., Vorotnikova, S., Vu, H.T.: Better algorithms for counting triangles in data streams. In: Milo, T., Tan, W. (eds.) Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26\u2013July 01, 2016, pp. 401\u2013411. ACM, New York (2016). https:\/\/doi.org\/10.1145\/2902251.2902283","DOI":"10.1145\/2902251.2902283"},{"issue":"4","key":"1246_CR21","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23\u201312327 (2014). https:\/\/doi.org\/10.1145\/2629620","journal-title":"J. ACM"},{"issue":"3","key":"1246_CR22","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"JF Buss","year":"1993","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM J. Comput. 22(3), 560\u2013572 (1993). https:\/\/doi.org\/10.1137\/0222038","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1246_CR23","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280\u2013301 (2001). https:\/\/doi.org\/10.1006\/jagm.2001.1186","journal-title":"J. Algorithms"},{"issue":"3","key":"1246_CR24","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1007\/s00453-016-0138-7","volume":"76","author":"V Guruswami","year":"2016","unstructured":"Guruswami, V., Onak, K.: Superlinear lower bounds for multipass graph processing. Algorithmica 76(3), 654\u2013683 (2016). https:\/\/doi.org\/10.1007\/s00453-016-0138-7","journal-title":"Algorithmica"},{"key":"1246_CR25","doi-asserted-by":"publisher","unstructured":"Assadi, S., Raz, R.: Near-quadratic lower bounds for two-pass graph streaming algorithms. In: Irani, S. (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16\u201319, 2020, pp. 342\u2013353. IEEE, Washington, DC (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00040","DOI":"10.1109\/FOCS46700.2020.00040"},{"key":"1246_CR26","doi-asserted-by":"publisher","unstructured":"Chen, L., Kol, G., Paramonov, D., Saxena, R.R., Song, Z., Yu, H.: Almost optimal super-constant-pass streaming lower bounds for reachability. In: Khuller, S., Williams, V.V. (eds.) STOC\u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021, pp. 570\u2013583. ACM, New York (2021). https:\/\/doi.org\/10.1145\/3406325.3451038","DOI":"10.1145\/3406325.3451038"},{"key":"1246_CR27","doi-asserted-by":"publisher","unstructured":"Verbin, E., Yu, W.: The streaming complexity of cycle counting, sorting by reversals, and other problems. In: Randall, D. (ed.) Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23\u201325, 2011, pp. 11\u201325. SIAM, Philadelphia (2011). https:\/\/doi.org\/10.1137\/1.9781611973082.2","DOI":"10.1137\/1.9781611973082.2"},{"issue":"5","key":"1246_CR28","doi-asserted-by":"publisher","first-page":"1965","DOI":"10.1007\/s00453-018-0520-8","volume":"81","author":"Z Huang","year":"2019","unstructured":"Huang, Z., Peng, P.: Dynamic graph stream algorithms in o(n) space. Algorithmica 81(5), 1965\u20131987 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0520-8","journal-title":"Algorithmica"},{"key":"1246_CR29","doi-asserted-by":"publisher","unstructured":"Assadi, S., Kol, G., Saxena, R.R., Yu, H.: Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems. In: Irani, S. (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16\u201319, 2020, pp. 354\u2013364. IEEE, Washington, DC (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00041","DOI":"10.1109\/FOCS46700.2020.00041"},{"key":"1246_CR30","doi-asserted-by":"publisher","unstructured":"Assadi, S., Vishvajeet, N.: Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. In: Khuller, S., Williams, V.V. (eds.) STOC\u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021, pp. 612\u2013625. ACM, New York (2021). https:\/\/doi.org\/10.1145\/3406325.3451110","DOI":"10.1145\/3406325.3451110"},{"key":"1246_CR31","doi-asserted-by":"crossref","unstructured":"Assadi, S., Chen, Y., Khanna, S.: Polynomial pass lower bounds for graph streaming algorithms. CoRR (2019). arXiv:abs\/1904.04720","DOI":"10.1145\/3313276.3316361"},{"key":"1246_CR32","doi-asserted-by":"publisher","unstructured":"Roditty, L., Williams, V.V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1\u20134, 2013, pp. 515\u2013524. ACM, New York (2013). https:\/\/doi.org\/10.1145\/2488608.2488673","DOI":"10.1145\/2488608.2488673"},{"issue":"8","key":"1246_CR33","doi-asserted-by":"publisher","first-page":"2292","DOI":"10.1007\/s00453-020-00680-z","volume":"82","author":"K Bringmann","year":"2020","unstructured":"Bringmann, K., Husfeldt, T., Magnusson, M.: Multivariate analysis of orthogonal range searching and graph distances. Algorithmica 82(8), 2292\u20132315 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00680-z","journal-title":"Algorithmica"},{"key":"1246_CR34","doi-asserted-by":"publisher","unstructured":"Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 377\u2013391. SIAM, Philadelphia (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch28","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"1246_CR35","doi-asserted-by":"publisher","unstructured":"Husfeldt, T.: Computing graph distances parameterized by treewidth and diameter. In: Guo, J., Hermelin, D. (eds.) 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24\u201326, 2016, Aarhus, Denmark. LIPIcs, vol. 63, pp. 16\u201311611. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2016). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.16","DOI":"10.4230\/LIPIcs.IPEC.2016.16"},{"issue":"3","key":"1246_CR36","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/3310228","volume":"15","author":"D Coudert","year":"2019","unstructured":"Coudert, D., Ducoffe, G., Popa, A.: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Trans. Algorithms 15(3), 33\u201313357 (2019). https:\/\/doi.org\/10.1145\/3310228","journal-title":"ACM Trans. Algorithms"},{"key":"1246_CR37","doi-asserted-by":"publisher","unstructured":"Bentert, M., Nichterlein, A.: Parameterized complexity of diameter. In: Heggernes, P. (ed.) Algorithms and Complexity\u201411th International Conference, CIAC 2019, Rome, Italy, May 27\u201329, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11485, pp. 50\u201361. Springer, Heidelberg (2019). https:\/\/doi.org\/10.1007\/978-3-030-17402-6_5","DOI":"10.1007\/978-3-030-17402-6_5"},{"issue":"2","key":"1246_CR38","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/3218821","volume":"15","author":"S Cabello","year":"2019","unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Trans. Algorithms 15(2), 21\u201312138 (2019). https:\/\/doi.org\/10.1145\/3218821","journal-title":"ACM Trans. Algorithms"},{"issue":"2\u20133","key":"1246_CR39","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0166-218X(00)00281-X","volume":"113","author":"DG Corneil","year":"2001","unstructured":"Corneil, D.G., Dragan, F.F., Habib, M., Paul, C.: Diameter determination on restricted graph families. Discrete Appl. Math. 113(2\u20133), 143\u2013166 (2001). https:\/\/doi.org\/10.1016\/S0166-218X(00)00281-X","journal-title":"Discrete Appl. Math."},{"key":"1246_CR40","doi-asserted-by":"publisher","unstructured":"Ducoffe, G.: Beyond helly graphs: The diameter problem on absolute retracts. In: Kowalik, L., Pilipczuk, M., Rzazewski, P. (eds.) Graph-Theoretic Concepts in Computer Science\u201447th International Workshop, WG 2021, Warsaw, Poland, June 23\u201325, 2021, Revised Selected Papers. Lecture Notes in Computer Science, vol. 12911, pp. 321\u2013335. Springer, Heidelberg (2021). https:\/\/doi.org\/10.1007\/978-3-030-86838-3_25","DOI":"10.1007\/978-3-030-86838-3_25"},{"issue":"3","key":"1246_CR41","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1002\/net.21998","volume":"77","author":"G Ducoffe","year":"2021","unstructured":"Ducoffe, G., Dragan, F.F.: A story of diameter, radius, and (almost) helly property. Networks 77(3), 435\u2013453 (2021). https:\/\/doi.org\/10.1002\/net.21998","journal-title":"Networks"},{"key":"1246_CR42","doi-asserted-by":"publisher","unstructured":"Ducoffe, G., Habib, M., Viennot, L.: Fast diameter computation within split graphs. In: Li, Y., Cardei, M., Huang, Y. (eds.) Combinatorial Optimization and Applications\u201413th International Conference, COCOA 2019, Xiamen, China, December 13\u201315, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11949, pp. 155\u2013167. Springer, Heidelberg (2019). https:\/\/doi.org\/10.1007\/978-3-030-36412-0_13","DOI":"10.1007\/978-3-030-36412-0_13"},{"key":"1246_CR43","doi-asserted-by":"publisher","unstructured":"Ducoffe, G., Habib, M., Viennot, L.: Diameter computation on H-minor free graphs and graphs of bounded (distance) vc-dimension. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5\u20138, 2020, pp. 1905\u20131922. SIAM, Philadelphia (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.117","DOI":"10.1137\/1.9781611975994.117"},{"issue":"2","key":"1246_CR44","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1137\/18M1193402","volume":"50","author":"P Gawrychowski","year":"2021","unstructured":"Gawrychowski, P., Kaplan, H., Mozes, S., Sharir, M., Weimann, O.: Voronoi diagrams on planar graphs, and computing the diameter in deterministic \u00f5(n$${}^{{5\/3}}$$) time. SIAM J. Comput. 50(2), 509\u2013554 (2021). https:\/\/doi.org\/10.1137\/18M1193402","journal-title":"SIAM J. Comput."},{"key":"1246_CR45","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"1246_CR46","doi-asserted-by":"crossref","unstructured":"Bishnu, A., Ghosh, A., Kolay, S., Mishra, G., Saurabh, S.: Fixed-parameter tractability of graph deletion problems over data streams. CoRR (2019). arXiv:abs\/1906.05458","DOI":"10.1007\/978-3-030-58150-3_53"},{"key":"1246_CR47","doi-asserted-by":"publisher","unstructured":"Chitnis, R.H., Cormode, G., Esfandiari, H., Hajiaghayi, M., Monemizadeh, M.: Brief announcement: New streaming algorithms for parameterized maximal matching and beyond. In: Blelloch, G.E., Agrawal, K. (eds.) Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13\u201315, 2015, pp. 56\u201358. ACM, New York (2015). https:\/\/doi.org\/10.1145\/2755573.2755618","DOI":"10.1145\/2755573.2755618"},{"key":"1246_CR48","unstructured":"Bishnu, A., Ghosh, A., Mishra, G., Sen, S.: On the streaming complexity of fundamental geometric problems. CoRR (2018). arXiv:1803.06875"},{"key":"1246_CR49","doi-asserted-by":"publisher","unstructured":"Agarwal, D., McGregor, A., Phillips, J.M., Venkatasubramanian, S., Zhu, Z.: Spatial scan statistics: approximations and performance study. In: Eliassi-Rad, T., Ungar, L.H., Craven, M., Gunopulos, D. (eds.) Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, August 20\u201323, 2006, pp. 24\u201333. ACM, New York (2006). https:\/\/doi.org\/10.1145\/1150402.1150410","DOI":"10.1145\/1150402.1150410"},{"key":"1246_CR50","doi-asserted-by":"publisher","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7\u201310 July 2003, Aarhus, Denmark, pp. 107\u2013117. IEEE Computer Society, Washington, DC (2003). https:\/\/doi.org\/10.1109\/CCC.2003.1214414","DOI":"10.1109\/CCC.2003.1214414"},{"issue":"1","key":"1246_CR51","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E., Jr.: Vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975). https:\/\/doi.org\/10.1007\/BF01580444","journal-title":"Math. Program."},{"key":"1246_CR52","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. In: Nagl, M., Perl, J. (eds.) Proceedings of the WG\u201983, International Workshop on Graphtheoretic Concepts in Computer Science, June 16\u201318, 1983, Haus Ohrbeck, Near Osnabr\u00fcck, Germany, pp. 17\u201328. Universit\u00e4tsverlag Rudolf Trauner, Linz (1983)"},{"key":"1246_CR53","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"JA Bondy","year":"1976","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Macmillan Education UK, London (1976). https:\/\/doi.org\/10.1007\/978-1-349-03521-2"},{"issue":"4","key":"1246_CR54","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n$${}^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973). https:\/\/doi.org\/10.1137\/0202019","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01246-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01246-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01246-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T07:05:53Z","timestamp":1725433553000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01246-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,19]]},"references-count":54,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["1246"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01246-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,6,19]]},"assertion":[{"value":"9 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 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"}}]}}