Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Wiktor Zuba, Grigorios Loukides, Solon P. Pissis, and Sharma V. Thankachan. Approximate Suffix-Prefix Dictionary Queries. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 85:1-85:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{zuba_et_al:LIPIcs.MFCS.2024.85, author = {Zuba, Wiktor and Loukides, Grigorios and Pissis, Solon P. and Thankachan, Sharma V.}, title = {{Approximate Suffix-Prefix Dictionary Queries}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {85:1--85:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.85}, URN = {urn:nbn:de:0030-drops-206416}, doi = {10.4230/LIPIcs.MFCS.2024.85}, annote = {Keywords: all-pairs suffix-prefix, suffix-prefix queries, suffix tree, k-errata tree} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Li Chen and Mingquan Ye. High-Accuracy Multicommodity Flows via Iterative Refinement. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.45, author = {Chen, Li and Ye, Mingquan}, title = {{High-Accuracy Multicommodity Flows via Iterative Refinement}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {45:1--45:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.45}, URN = {urn:nbn:de:0030-drops-201887}, doi = {10.4230/LIPIcs.ICALP.2024.45}, annote = {Keywords: High-accuracy multicommodity flow, Iterative refinement framework, Convex flow solver} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yu Chen, Michael Kapralov, Mikhail Makarov, and Davide Mazzali. On the Streaming Complexity of Expander Decomposition. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.46, author = {Chen, Yu and Kapralov, Michael and Makarov, Mikhail and Mazzali, Davide}, title = {{On the Streaming Complexity of Expander Decomposition}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {46:1--46:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.46}, URN = {urn:nbn:de:0030-drops-201890}, doi = {10.4230/LIPIcs.ICALP.2024.46}, annote = {Keywords: Graph Sketching, Dynamic Streaming, Expander Decomposition} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Michal Dory, Sebastian Forster, Yasamin Nazari, and Tijn de Vos. New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 58:1-58:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dory_et_al:LIPIcs.ICALP.2024.58, author = {Dory, Michal and Forster, Sebastian and Nazari, Yasamin and de Vos, Tijn}, title = {{New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {58:1--58:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.58}, URN = {urn:nbn:de:0030-drops-202012}, doi = {10.4230/LIPIcs.ICALP.2024.58}, annote = {Keywords: Decremental Shortest Path, All-Pairs Shortest Paths} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Optimal Electrical Oblivious Routing on Expanders. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 65:1-65:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{florescu_et_al:LIPIcs.ICALP.2024.65, author = {Florescu, Cella and Kyng, Rasmus and Gutenberg, Maximilian Probst and Sachdeva, Sushant}, title = {{Optimal Electrical Oblivious Routing on Expanders}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {65:1--65:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.65}, URN = {urn:nbn:de:0030-drops-202083}, doi = {10.4230/LIPIcs.ICALP.2024.65}, annote = {Keywords: Expanders, Oblivious routing for 𝓁\underlinep, Electrical flow routing} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Adam Karczmarz and Marcin Smulewicz. Fully Dynamic Strongly Connected Components in Planar Digraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{karczmarz_et_al:LIPIcs.ICALP.2024.95, author = {Karczmarz, Adam and Smulewicz, Marcin}, title = {{Fully Dynamic Strongly Connected Components in Planar Digraphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {95:1--95:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.95}, URN = {urn:nbn:de:0030-drops-202388}, doi = {10.4230/LIPIcs.ICALP.2024.95}, annote = {Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability, planar graphs} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. Electrical Flows for Polylogarithmic Competitive Oblivious Routing. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 55:1-55:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{goranci_et_al:LIPIcs.ITCS.2024.55, author = {Goranci, Gramoz and Henzinger, Monika and R\"{a}cke, Harald and Sachdeva, Sushant and Sricharan, A. R.}, title = {{Electrical Flows for Polylogarithmic Competitive Oblivious Routing}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {55:1--55:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.55}, URN = {urn:nbn:de:0030-drops-195830}, doi = {10.4230/LIPIcs.ITCS.2024.55}, annote = {Keywords: oblivious routing, electrical flows} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Sebastian Forster, Gramoz Goranci, Yasamin Nazari, and Antonis Skarlatos. Bootstrapping Dynamic Distance Oracles. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{forster_et_al:LIPIcs.ESA.2023.50, author = {Forster, Sebastian and Goranci, Gramoz and Nazari, Yasamin and Skarlatos, Antonis}, title = {{Bootstrapping Dynamic Distance Oracles}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {50:1--50:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.50}, URN = {urn:nbn:de:0030-drops-187031}, doi = {10.4230/LIPIcs.ESA.2023.50}, annote = {Keywords: Dynamic graph algorithms, Distance Oracles, Shortest Paths} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Gramoz Goranci and Monika Henzinger. Efficient Data Structures for Incremental Exact and Approximate Maximum Flow. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{goranci_et_al:LIPIcs.ICALP.2023.69, author = {Goranci, Gramoz and Henzinger, Monika}, title = {{Efficient Data Structures for Incremental Exact and Approximate Maximum Flow}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {69:1--69:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.69}, URN = {urn:nbn:de:0030-drops-181212}, doi = {10.4230/LIPIcs.ICALP.2023.69}, annote = {Keywords: dynamic graph algorithms, maximum flow, data structures} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bernstein_et_al:LIPIcs.ICALP.2022.20, author = {Bernstein, Aaron and van den Brand, Jan and Probst Gutenberg, Maximilian and Nanongkai, Danupon and Saranurak, Thatchaphol and Sidford, Aaron and Sun, He}, title = {{Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {20:1--20:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.20}, URN = {urn:nbn:de:0030-drops-163611}, doi = {10.4230/LIPIcs.ICALP.2022.20}, annote = {Keywords: dynamic graph algorithm, adaptive adversary, spanner, sparsifier} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Gramoz Goranci, Monika Henzinger, and Dariusz Leniowski. A Tree Structure For Dynamic Facility Location. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 39:1-39:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{goranci_et_al:LIPIcs.ESA.2018.39, author = {Goranci, Gramoz and Henzinger, Monika and Leniowski, Dariusz}, title = {{A Tree Structure For Dynamic Facility Location}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {39:1--39:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.39}, URN = {urn:nbn:de:0030-drops-95026}, doi = {10.4230/LIPIcs.ESA.2018.39}, annote = {Keywords: facility location, dynamic algorithm, approximation, doubling dimension} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Gramoz Goranci, Monika Henzinger, and Pan Peng. Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{goranci_et_al:LIPIcs.ESA.2018.40, author = {Goranci, Gramoz and Henzinger, Monika and Peng, Pan}, title = {{Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {40:1--40:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.40}, URN = {urn:nbn:de:0030-drops-95036}, doi = {10.4230/LIPIcs.ESA.2018.40}, annote = {Keywords: Dynamic graph algorithms, effective resistance, separable graphs, Schur complement, conditional lower bounds} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Gramoz Goranci, Monika Henzinger, and Pan Peng. Improved Guarantees for Vertex Sparsification in Planar Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{goranci_et_al:LIPIcs.ESA.2017.44, author = {Goranci, Gramoz and Henzinger, Monika and Peng, Pan}, title = {{Improved Guarantees for Vertex Sparsification in Planar Graphs}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {44:1--44:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.44}, URN = {urn:nbn:de:0030-drops-78337}, doi = {10.4230/LIPIcs.ESA.2017.44}, annote = {Keywords: Vertex Sparsification, Graph Sparsification, Planar Graphs, Metric Embedding, Reachability} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Gramoz Goranci, Monika Henzinger, and Pan Peng. The Power of Vertex Sparsifiers in Dynamic Graph Algorithms. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{goranci_et_al:LIPIcs.ESA.2017.45, author = {Goranci, Gramoz and Henzinger, Monika and Peng, Pan}, title = {{The Power of Vertex Sparsifiers in Dynamic Graph Algorithms}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {45:1--45:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.45}, URN = {urn:nbn:de:0030-drops-78460}, doi = {10.4230/LIPIcs.ESA.2017.45}, annote = {Keywords: Dynamic graph algorithms, electrical flow, minor-free graphs, max flow} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Yun Kuen Cheung, Gramoz Goranci, and Monika Henzinger. Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 131:1-131:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{cheung_et_al:LIPIcs.ICALP.2016.131, author = {Cheung, Yun Kuen and Goranci, Gramoz and Henzinger, Monika}, title = {{Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {131:1--131:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.131}, URN = {urn:nbn:de:0030-drops-62675}, doi = {10.4230/LIPIcs.ICALP.2016.131}, annote = {Keywords: Distance Approximating Minor, Graph Minor, Graph Compression, Vertex Sparsification, Metric Embedding} }
Feedback for Dagstuhl Publishing