LIPIcs, Volume 129
SoCG 2019, June 18-21, 2019, Portland, Oregon, USA
Editors: Gill Barequet and Yusu Wang
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Lotte Blank and Anne Driemel. A Faster Algorithm for the Fréchet Distance in 1D for the Imbalanced Case. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{blank_et_al:LIPIcs.ESA.2024.28, author = {Blank, Lotte and Driemel, Anne}, title = {{A Faster Algorithm for the Fr\'{e}chet Distance in 1D for the Imbalanced Case}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {28:1--28:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.28}, URN = {urn:nbn:de:0030-drops-210999}, doi = {10.4230/LIPIcs.ESA.2024.28}, annote = {Keywords: \{Fr\'{e}chet distance\}, distance oracle, data structures, time series} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Jean-Daniel Boissonnat and Kunal Dutta. A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{boissonnat_et_al:LIPIcs.ESA.2024.29, author = {Boissonnat, Jean-Daniel and Dutta, Kunal}, title = {{A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {29:1--29:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.29}, URN = {urn:nbn:de:0030-drops-211009}, doi = {10.4230/LIPIcs.ESA.2024.29}, annote = {Keywords: Persistent homology, Gaussian kernels, Random Fourier Features, Euclidean embedding} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Hybrid k-Clustering: Blending k-Median and k-Center. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fomin_et_al:LIPIcs.APPROX/RANDOM.2024.4, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav}, title = {{Hybrid k-Clustering: Blending k-Median and k-Center}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.4}, URN = {urn:nbn:de:0030-drops-209975}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.4}, annote = {Keywords: clustering, k-center, k-median, Euclidean space, fpt approximation} }
Published in: Dagstuhl Reports, Volume 14, Issue 2 (2024)
Paweł Dłotko, Dmitry Feichtner-Kozlov, Anastasios Stefanou, Yusu Wang, and Jan F Senge. Applied and Combinatorial Topology (Dagstuhl Seminar 24092). In Dagstuhl Reports, Volume 14, Issue 2, pp. 206-239, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{dlotko_et_al:DagRep.14.2.206, author = {D{\l}otko, Pawe{\l} and Feichtner-Kozlov, Dmitry and Stefanou, Anastasios and Wang, Yusu and Senge, Jan F}, title = {{Applied and Combinatorial Topology (Dagstuhl Seminar 24092)}}, pages = {206--239}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2024}, volume = {14}, number = {2}, editor = {D{\l}otko, Pawe{\l} and Feichtner-Kozlov, Dmitry and Stefanou, Anastasios and Wang, Yusu and Senge, Jan F}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.2.206}, URN = {urn:nbn:de:0030-drops-205059}, doi = {10.4230/DagRep.14.2.206}, annote = {Keywords: Applied Topology, Topological Data Analysis, Discrete Morse Theory, Combinatorial Topology, Statistics} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt. Algorithms for Gradual Polyline Simplification. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{krumbholz_et_al:LIPIcs.SEA.2024.19, author = {Krumbholz, Nick and Funke, Stefan and Sch\"{a}fer, Peter and Storandt, Sabine}, title = {{Algorithms for Gradual Polyline Simplification}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {19:1--19:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.19}, URN = {urn:nbn:de:0030-drops-203847}, doi = {10.4230/LIPIcs.SEA.2024.19}, annote = {Keywords: Polyline simplification, Progressive simplification, Fr\'{e}chet distance} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Aziz Burak Gülen, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. A Generalization of the Persistent Laplacian to Simplicial Maps. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gulen_et_al:LIPIcs.SoCG.2023.37, author = {G\"{u}len, Aziz Burak and M\'{e}moli, Facundo and Wan, Zhengchao and Wang, Yusu}, title = {{A Generalization of the Persistent Laplacian to Simplicial Maps}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {37:1--37:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.37}, URN = {urn:nbn:de:0030-drops-178877}, doi = {10.4230/LIPIcs.SoCG.2023.37}, annote = {Keywords: combinatorial Laplacian, persistent Laplacian, Schur complement, persistent homology, persistent Betti number} }
Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)
Samantha Chen and Yusu Wang. Approximation Algorithms for 1-Wasserstein Distance Between Persistence Diagrams. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.SEA.2021.14, author = {Chen, Samantha and Wang, Yusu}, title = {{Approximation Algorithms for 1-Wasserstein Distance Between Persistence Diagrams}}, booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)}, pages = {14:1--14:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-185-6}, ISSN = {1868-8969}, year = {2021}, volume = {190}, editor = {Coudert, David and Natale, Emanuele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.14}, URN = {urn:nbn:de:0030-drops-137861}, doi = {10.4230/LIPIcs.SEA.2021.14}, annote = {Keywords: persistence diagrams, approximation algorithms, Wasserstein distance, optimal transport} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Ulrich Bauer, Claudia Landi, and Facundo Mémoli. The Reeb Graph Edit Distance Is Universal. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bauer_et_al:LIPIcs.SoCG.2020.15, author = {Bauer, Ulrich and Landi, Claudia and M\'{e}moli, Facundo}, title = {{The Reeb Graph Edit Distance Is Universal}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {15:1--15:16}, 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.15}, URN = {urn:nbn:de:0030-drops-121730}, doi = {10.4230/LIPIcs.SoCG.2020.15}, annote = {Keywords: Reeb graphs, topological descriptors, edit distance, interleaving distance} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang. Elder-Rule-Staircodes for Augmented Metric Spaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cai_et_al:LIPIcs.SoCG.2020.26, author = {Cai, Chen and Kim, Woojin and M\'{e}moli, Facundo and Wang, Yusu}, title = {{Elder-Rule-Staircodes for Augmented Metric Spaces}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {26:1--26:17}, 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.26}, URN = {urn:nbn:de:0030-drops-121848}, doi = {10.4230/LIPIcs.SoCG.2020.26}, annote = {Keywords: Persistent homology, Multiparameter persistence, Barcodes, Elder rule, Hierarchical clustering, Graded Betti numbers} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Tamal K. Dey, Tianqi Li, and Yusu Wang. An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dey_et_al:LIPIcs.SoCG.2020.36, author = {Dey, Tamal K. and Li, Tianqi and Wang, Yusu}, title = {{An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {36:1--36:15}, 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.36}, URN = {urn:nbn:de:0030-drops-121944}, doi = {10.4230/LIPIcs.SoCG.2020.36}, annote = {Keywords: computational topology, directed graph, path homology, persistent path homology} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Matthew Kahle, Minghao Tian, and Yusu Wang. Local Cliques in ER-Perturbed Random Geometric Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kahle_et_al:LIPIcs.ISAAC.2019.29, author = {Kahle, Matthew and Tian, Minghao and Wang, Yusu}, title = {{Local Cliques in ER-Perturbed Random Geometric Graphs}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {29:1--29:22}, 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.29}, URN = {urn:nbn:de:0030-drops-115253}, doi = {10.4230/LIPIcs.ISAAC.2019.29}, annote = {Keywords: random graphs, random geometric graphs, edge clique number, the probabilistic method, metric recovery} }
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 129, 35th International Symposium on Computational Geometry (SoCG 2019)
35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Proceedings{barequet_et_al:LIPIcs.SoCG.2019, title = {{LIPIcs, Volume 129, SoCG'19, Complete Volume}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019}, URN = {urn:nbn:de:0030-drops-105562}, doi = {10.4230/LIPIcs.SoCG.2019}, annote = {Keywords: Theory of computation, Computational geometry, Design and analysis of algorithms, Mathematics of computing, Combinatorics, Graph algortihms} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{barequet_et_al:LIPIcs.SoCG.2019.0, author = {Barequet, Gill and Wang, Yusu}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.0}, URN = {urn:nbn:de:0030-drops-104047}, doi = {10.4230/LIPIcs.SoCG.2019.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Feedback for Dagstuhl Publishing