Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, and Sorrachai Yingchareonthawornchai. The Group Access Bounds for Binary Search Trees. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2024.38, author = {Chalermsook, Parinya and Gupta, Manoj and Jiamjitrak, Wanchote and Pareek, Akash and Yingchareonthawornchai, Sorrachai}, title = {{The Group Access Bounds for Binary Search Trees}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {38:1--38:18}, 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.38}, URN = {urn:nbn:de:0030-drops-201817}, doi = {10.4230/LIPIcs.ICALP.2024.38}, annote = {Keywords: Dynamic Optimality, Binary Search Tree, Online Algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Itai Boneh, Shay Golan, Shay Mozes, and Oren Weimann. Õptimal Dynamic Time Warping on Run-Length Encoded Strings. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{boneh_et_al:LIPIcs.ICALP.2024.30, author = {Boneh, Itai and Golan, Shay and Mozes, Shay and Weimann, Oren}, title = {{\~{O}ptimal Dynamic Time Warping on Run-Length Encoded Strings}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {30:1--30:17}, 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.30}, URN = {urn:nbn:de:0030-drops-201730}, doi = {10.4230/LIPIcs.ICALP.2024.30}, annote = {Keywords: Dynamic time warping, Fr\'{e}chet distance, edit distance, run-length encoding} }
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 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Kyle Fox, Hongyao Huang, and Benjamin Raichel. Clustering with Faulty Centers. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fox_et_al:LIPIcs.ISAAC.2022.10, author = {Fox, Kyle and Huang, Hongyao and Raichel, Benjamin}, title = {{Clustering with Faulty Centers}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {10:1--10:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.10}, URN = {urn:nbn:de:0030-drops-172950}, doi = {10.4230/LIPIcs.ISAAC.2022.10}, annote = {Keywords: clustering, approximation, probabilistic input, uncertain input} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Kyle Fox and Thomas Stanley. Computation of Cycle Bases in Surface Embedded Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fox_et_al:LIPIcs.ISAAC.2022.13, author = {Fox, Kyle and Stanley, Thomas}, title = {{Computation of Cycle Bases in Surface Embedded Graphs}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.13}, URN = {urn:nbn:de:0030-drops-172982}, doi = {10.4230/LIPIcs.ISAAC.2022.13}, annote = {Keywords: cycle basis, surface embedded graphs, homology} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Julian Enoch, Kyle Fox, Dor Mesica, and Shay Mozes. A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 72:1-72:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{enoch_et_al:LIPIcs.ISAAC.2021.72, author = {Enoch, Julian and Fox, Kyle and Mesica, Dor and Mozes, Shay}, title = {{A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {72:1--72:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.72}, URN = {urn:nbn:de:0030-drops-155057}, doi = {10.4230/LIPIcs.ISAAC.2021.72}, annote = {Keywords: flow, planar graphs, vertex capacities} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Connor Colombe and Kyle Fox. Approximating the (Continuous) Fréchet Distance. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{colombe_et_al:LIPIcs.SoCG.2021.26, author = {Colombe, Connor and Fox, Kyle}, title = {{Approximating the (Continuous) Fr\'{e}chet Distance}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {26:1--26:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.26}, URN = {urn:nbn:de:0030-drops-138259}, doi = {10.4230/LIPIcs.SoCG.2021.26}, annote = {Keywords: Fr\'{e}chet distance, approximation algorithm, approximate decision procedure} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Kyle Fox and Jiashuai Lu. A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fox_et_al:LIPIcs.SoCG.2020.45, author = {Fox, Kyle and Lu, Jiashuai}, title = {{A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {45:1--45:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.45}, URN = {urn:nbn:de:0030-drops-122034}, doi = {10.4230/LIPIcs.SoCG.2020.45}, annote = {Keywords: Transportation map, earth mover’s distance, shape matching, approximation algorithms} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Kyle Fox and Xinyi Li. Approximating the Geometric Edit Distance. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fox_et_al:LIPIcs.ISAAC.2019.23, author = {Fox, Kyle and Li, Xinyi}, title = {{Approximating the Geometric Edit Distance}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {23:1--23:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.23}, URN = {urn:nbn:de:0030-drops-115195}, doi = {10.4230/LIPIcs.ISAAC.2019.23}, annote = {Keywords: Geometric edit distance, Approximation, Randomized algorithms} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Elena Farahbakhsh Touli and Yusu Wang. FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{farahbakhshtouli_et_al:LIPIcs.ESA.2019.83, author = {Farahbakhsh Touli, Elena and Wang, Yusu}, title = {{FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {83:1--83:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.83}, URN = {urn:nbn:de:0030-drops-112048}, doi = {10.4230/LIPIcs.ESA.2019.83}, annote = {Keywords: Gromov-Hausdorff distance, Interleaving distance, Merge trees} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Pankaj K. Agarwal, Kyle Fox, and Abhinandan Nath. Maintaining Reeb Graphs of Triangulated 2-Manifolds. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{agarwal_et_al:LIPIcs.FSTTCS.2017.8, author = {Agarwal, Pankaj K. and Fox, Kyle and Nath, Abhinandan}, title = {{Maintaining Reeb Graphs of Triangulated 2-Manifolds}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.8}, URN = {urn:nbn:de:0030-drops-84043}, doi = {10.4230/LIPIcs.FSTTCS.2017.8}, annote = {Keywords: Reeb graphs, 2-manifolds, topological graph theory} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. Faster Algorithms for the Geometric Transportation Problem. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2017.7, author = {Agarwal, Pankaj K. and Fox, Kyle and Panigrahi, Debmalya and Varadarajan, Kasturi R. and Xiao, Allen}, title = {{Faster Algorithms for the Geometric Transportation Problem}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.7}, URN = {urn:nbn:de:0030-drops-72344}, doi = {10.4230/LIPIcs.SoCG.2017.7}, annote = {Keywords: transportation map, earth mover's distance, shape matching, approximation algorithms} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2016.6, author = {Agarwal, Pankaj K. and Fox, Kyle and Pan, Jiangwei and Ying, Rex}, title = {{Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {6:1--6:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.6}, URN = {urn:nbn:de:0030-drops-58989}, doi = {10.4230/LIPIcs.SoCG.2016.6}, annote = {Keywords: Dynamic time warping, Edit distance, Near-linear-time algorithm, Dynamic programming, Well-separated pair decomposition} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, and Amir Nayyeri. Minimum Cycle and Homology Bases of Surface Embedded Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{borradaile_et_al:LIPIcs.SoCG.2016.23, author = {Borradaile, Glencora and Chambers, Erin Wolf and Fox, Kyle and Nayyeri, Amir}, title = {{Minimum Cycle and Homology Bases of Surface Embedded Graphs}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {23:1--23:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.23}, URN = {urn:nbn:de:0030-drops-59152}, doi = {10.4230/LIPIcs.SoCG.2016.23}, annote = {Keywords: Cycle basis, Homology basis, Topological graph theory} }