[{"type":"conference","date_published":"2017-09-01T00:00:00Z","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-049-1"]},"oa":1,"main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2017.44","open_access":"1"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"later_version","id":"11894","status":"public"}]},"publication":"25th Annual European Symposium on Algorithms","oa_version":"Published Version","article_number":"44","month":"09","language":[{"iso":"eng"}],"conference":{"start_date":"2017-09-04","name":"ESA: Annual European Symposium on Algorithms","end_date":"2017-09-06","location":"Vienna, Austria"},"citation":{"chicago":"Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” In <i>25th Annual European Symposium on Algorithms</i>, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.44\">https://doi.org/10.4230/LIPICS.ESA.2017.44</a>.","ieee":"G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” in <i>25th Annual European Symposium on Algorithms</i>, Vienna, Austria, 2017, vol. 87.","apa":"Goranci, G., Henzinger, M. H., &#38; Peng, P. (2017). Improved guarantees for vertex sparsification in planar graphs. In <i>25th Annual European Symposium on Algorithms</i> (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.44\">https://doi.org/10.4230/LIPICS.ESA.2017.44</a>","ama":"Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification in planar graphs. In: <i>25th Annual European Symposium on Algorithms</i>. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.44\">10.4230/LIPICS.ESA.2017.44</a>","ista":"Goranci G, Henzinger MH, Peng P. 2017. Improved guarantees for vertex sparsification in planar graphs. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 44.","short":"G. Goranci, M.H. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” <i>25th Annual European Symposium on Algorithms</i>, vol. 87, 44, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.44\">10.4230/LIPICS.ESA.2017.44</a>."},"year":"2017","date_updated":"2023-02-21T16:32:16Z","external_id":{"arxiv":["1702.01136"]},"day":"01","arxiv":1,"doi":"10.4230/LIPICS.ESA.2017.44","abstract":[{"lang":"eng","text":"Graph Sparsification aims at compressing large graphs into smaller ones while (approximately) preserving important characteristics of the input graph. In this work we study Vertex Sparsifiers, i.e., sparsifiers whose goal is to reduce the number of vertices. Given a weighted graph G=(V,E), and a terminal set K with |K|=k, a quality-q vertex cut sparsifier of G is a graph H with K contained in V_H that preserves the value of minimum cuts separating any bipartition of K, up to a factor of q. We show that planar graphs with all the k terminals lying on the same face admit quality-1 vertex cut sparsifier of size O(k^2) that are also planar. Our result extends to vertex flow and distance sparsifiers. It improves the previous best known bound of O(k^2 2^(2k)) for cut and flow sparsifiers by an exponential factor, and matches an Omega(k^2) lower-bound for this class of graphs.\r\n\r\nWe also study vertex reachability sparsifiers for directed graphs. Given a digraph G=(V,E) and a terminal set K, a vertex reachability sparsifier of G is a digraph H=(V_H,E_H), K contained in V_H that preserves all reachability information among terminal pairs. We introduce the notion of reachability-preserving minors, i.e., we require H to be a minor of G. Among others, for general planar digraphs, we construct reachability-preserving minors of size O(k^2 log^2 k). We complement our upper-bound by showing that there exists an infinite family of acyclic planar digraphs such that any reachability-preserving minor must have Omega(k^2) vertices."}],"volume":87,"extern":"1","scopus_import":"1","_id":"11831","author":[{"last_name":"Goranci","first_name":"Gramoz","full_name":"Goranci, Gramoz"},{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Peng, Pan","first_name":"Pan","last_name":"Peng"}],"date_created":"2022-08-12T09:27:11Z","article_processing_charge":"No","publication_status":"published","intvolume":"        87","alternative_title":["LIPIcs"],"title":"Improved guarantees for vertex sparsification in planar graphs","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"conference":{"start_date":"2017-09-04","name":"ESA: Annual European Symposium on Algorithms","location":"Vienna, Austria","end_date":"2017-09-06"},"language":[{"iso":"eng"}],"oa_version":"Published Version","month":"09","article_number":"48","publication":"25th Annual European Symposium on Algorithms","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPICS.ESA.2017.48"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["978-3-95977-049-1"],"issn":["1868-8969"]},"oa":1,"date_published":"2017-09-01T00:00:00Z","type":"conference","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","publication_status":"published","date_created":"2022-08-12T09:58:46Z","article_processing_charge":"No","title":"Dynamic clustering to minimize the sum of radii","alternative_title":["LIPIcs"],"intvolume":"        87","_id":"11832","scopus_import":"1","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":"Dariusz","last_name":"Leniowski","full_name":"Leniowski, Dariusz"},{"first_name":"Claire","last_name":"Mathieu","full_name":"Mathieu, Claire"}],"volume":87,"extern":"1","arxiv":1,"doi":"10.4230/LIPICS.ESA.2017.48","day":"01","abstract":[{"text":"In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem.\r\n\r\nWe present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem.","lang":"eng"}],"date_updated":"2023-02-16T11:54:12Z","year":"2017","citation":{"ista":"Henzinger MH, Leniowski D, Mathieu C. 2017. Dynamic clustering to minimize the sum of radii. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 48.","short":"M.H. Henzinger, D. Leniowski, C. Mathieu, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Henzinger, Monika H., et al. “Dynamic Clustering to Minimize the Sum of Radii.” <i>25th Annual European Symposium on Algorithms</i>, vol. 87, 48, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.48\">10.4230/LIPICS.ESA.2017.48</a>.","chicago":"Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” In <i>25th Annual European Symposium on Algorithms</i>, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.48\">https://doi.org/10.4230/LIPICS.ESA.2017.48</a>.","ieee":"M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” in <i>25th Annual European Symposium on Algorithms</i>, Vienna, Austria, 2017, vol. 87.","apa":"Henzinger, M. H., Leniowski, D., &#38; Mathieu, C. (2017). Dynamic clustering to minimize the sum of radii. In <i>25th Annual European Symposium on Algorithms</i> (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.48\">https://doi.org/10.4230/LIPICS.ESA.2017.48</a>","ama":"Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. In: <i>25th Annual European Symposium on Algorithms</i>. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.48\">10.4230/LIPICS.ESA.2017.48</a>"},"external_id":{"arxiv":["1707.02577"]}},{"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2017.45","open_access":"1"}],"type":"conference","date_published":"2017-09-01T00:00:00Z","oa":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-049-1"]},"language":[{"iso":"eng"}],"conference":{"start_date":"2017-09-04","name":"ESA: Annual European Symposium on Algorithms","location":"Vienna, Austria","end_date":"2017-09-06"},"publication":"25th Annual European Symposium on Algorithms","article_number":"45","month":"09","oa_version":"Published Version","extern":"1","volume":87,"external_id":{"arxiv":["1712.06473"]},"year":"2017","citation":{"ista":"Goranci G, Henzinger MH, Peng P. 2017. The power of vertex sparsifiers in dynamic graph algorithms. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 45.","mla":"Goranci, Gramoz, et al. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.” <i>25th Annual European Symposium on Algorithms</i>, vol. 87, 45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.45\">10.4230/LIPICS.ESA.2017.45</a>.","short":"G. Goranci, M.H. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","chicago":"Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “The Power of Vertex Sparsifiers in Dynamic Graph Algorithms.” In <i>25th Annual European Symposium on Algorithms</i>, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.45\">https://doi.org/10.4230/LIPICS.ESA.2017.45</a>.","ieee":"G. Goranci, M. H. Henzinger, and P. Peng, “The power of vertex sparsifiers in dynamic graph algorithms,” in <i>25th Annual European Symposium on Algorithms</i>, Vienna, Austria, 2017, vol. 87.","apa":"Goranci, G., Henzinger, M. H., &#38; Peng, P. (2017). The power of vertex sparsifiers in dynamic graph algorithms. In <i>25th Annual European Symposium on Algorithms</i> (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.45\">https://doi.org/10.4230/LIPICS.ESA.2017.45</a>","ama":"Goranci G, Henzinger MH, Peng P. The power of vertex sparsifiers in dynamic graph algorithms. In: <i>25th Annual European Symposium on Algorithms</i>. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPICS.ESA.2017.45\">10.4230/LIPICS.ESA.2017.45</a>"},"date_updated":"2023-02-16T11:56:37Z","abstract":[{"text":"We introduce a new algorithmic framework for designing dynamic graph algorithms in minor-free graphs, by exploiting the structure of such graphs and a tool called vertex sparsification, which is a way to compress large graphs into small ones that well preserve relevant properties among a subset of vertices and has previously mainly been used in the design of approximation algorithms.\r\n\r\nUsing this framework, we obtain a Monte Carlo randomized fully dynamic algorithm for (1 + epsilon)-approximating the energy of electrical flows in n-vertex planar graphs with tilde{O}(r epsilon^{-2}) worst-case update time and tilde{O}((r + n / sqrt{r}) epsilon^{-2}) worst-case query time, for any r larger than some constant. For r=n^{2/3}, this gives tilde{O}(n^{2/3} epsilon^{-2}) update time and tilde{O}(n^{2/3} epsilon^{-2}) query time. We also extend this algorithm to work for minor-free graphs with similar approximation and running time guarantees. Furthermore, we illustrate our framework on the all-pairs max flow and shortest path problems by giving corresponding dynamic algorithms in minor-free graphs with both sublinear update and query times. To the best of our knowledge, our results are the first to systematically establish such a connection between dynamic graph algorithms and vertex sparsification.\r\n\r\nWe also present both upper bound and lower bound for maintaining the energy of electrical flows in the incremental subgraph model, where updates consist of only vertex activations, which might be of independent interest.","lang":"eng"}],"day":"01","arxiv":1,"doi":"10.4230/LIPICS.ESA.2017.45","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"last_name":"Goranci","first_name":"Gramoz","full_name":"Goranci, Gramoz"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"full_name":"Peng, Pan","last_name":"Peng","first_name":"Pan"}],"scopus_import":"1","_id":"11833","intvolume":"        87","title":"The power of vertex sparsifiers in dynamic graph algorithms","alternative_title":["LIPIcs"],"article_processing_charge":"No","date_created":"2022-08-12T10:46:26Z","publication_status":"published"}]