Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Adil Chhabra, Marcelo Fonseca Faraj, Christian Schulz, and Daniel Seemaier. Buffered Streaming Edge Partitioning. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chhabra_et_al:LIPIcs.SEA.2024.5, author = {Chhabra, Adil and Fonseca Faraj, Marcelo and Schulz, Christian and Seemaier, Daniel}, title = {{Buffered Streaming Edge Partitioning}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {5:1--5:21}, 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.5}, URN = {urn:nbn:de:0030-drops-203701}, doi = {10.4230/LIPIcs.SEA.2024.5}, annote = {Keywords: graph partitioning, edge partitioning, streaming, online, buffered partitioning} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani. Faster Treewidth-Based Approximations for Wiener Index. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{conrado_et_al:LIPIcs.SEA.2024.6, author = {Conrado, Giovanna Kobus and Goharshady, Amir Kafshdar and Hudec, Pavel and Li, Pingjiang and Motwani, Harshit Jitendra}, title = {{Faster Treewidth-Based Approximations for Wiener Index}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {6:1--6:19}, 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.6}, URN = {urn:nbn:de:0030-drops-203718}, doi = {10.4230/LIPIcs.SEA.2024.6}, annote = {Keywords: Computational Chemistry, Treewidth, Wiener Index} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Marcelo Fonseca Faraj, Ernestine Großmann, Felix Joos, Thomas Möller, and Christian Schulz. Engineering Weighted Connectivity Augmentation Algorithms. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{faraj_et_al:LIPIcs.SEA.2024.11, author = {Faraj, Marcelo Fonseca and Gro{\ss}mann, Ernestine and Joos, Felix and M\"{o}ller, Thomas and Schulz, Christian}, title = {{Engineering Weighted Connectivity Augmentation Algorithms}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {11:1--11:22}, 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.11}, URN = {urn:nbn:de:0030-drops-203768}, doi = {10.4230/LIPIcs.SEA.2024.11}, annote = {Keywords: weighted connectivity augmentation, approximation, heuristic, integer linear program, algorithm engineering} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The Discrepancy of Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.27, author = {Bodwin, Greg and Deng, Chengyuan and Gao, Jie and Hoppenworth, Gary and Upadhyay, Jalaj and Wang, Chen}, title = {{The Discrepancy of Shortest Paths}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {27:1--27: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.27}, URN = {urn:nbn:de:0030-drops-201705}, doi = {10.4230/LIPIcs.ICALP.2024.27}, annote = {Keywords: Discrepancy, hereditary discrepancy, shortest paths, differential privacy} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Tsvi Kopelowitz, Ariel Korin, and Liam Roditty. On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 101:1-101:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kopelowitz_et_al:LIPIcs.ICALP.2024.101, author = {Kopelowitz, Tsvi and Korin, Ariel and Roditty, Liam}, title = {{On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {101:1--101: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.101}, URN = {urn:nbn:de:0030-drops-202443}, doi = {10.4230/LIPIcs.ICALP.2024.101}, annote = {Keywords: Graph algorithms, Approximate distance oracle, data structures, shortest path} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Benjamin Scheidt. On Homomorphism Indistinguishability and Hypertree Depth. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 152:1-152:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{scheidt:LIPIcs.ICALP.2024.152, author = {Scheidt, Benjamin}, title = {{On Homomorphism Indistinguishability and Hypertree Depth}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {152:1--152: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.152}, URN = {urn:nbn:de:0030-drops-202958}, doi = {10.4230/LIPIcs.ICALP.2024.152}, annote = {Keywords: homomorphism indistinguishability, counting logics, guarded logics, hypergraphs, incidence graphs, tree depth, elimination forest, hypertree width} }
Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)
Valentin Buchhold and Dorothea Wagner. Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{buchhold_et_al:LIPIcs.SEA.2021.18, author = {Buchhold, Valentin and Wagner, Dorothea}, title = {{Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications}}, booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)}, pages = {18:1--18:18}, 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.18}, URN = {urn:nbn:de:0030-drops-137908}, doi = {10.4230/LIPIcs.SEA.2021.18}, annote = {Keywords: Nearest neighbors, points of interest, travel demand generation, radiation model, customizable contraction hierarchies} }
Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. An Efficient Solution for One-To-Many Multi-Modal Journey Planning. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{sauer_et_al:OASIcs.ATMOS.2020.1, author = {Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias}, title = {{An Efficient Solution for One-To-Many Multi-Modal Journey Planning}}, booktitle = {20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)}, pages = {1:1--1:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-170-2}, ISSN = {2190-6807}, year = {2020}, volume = {85}, editor = {Huisman, Dennis and Zaroliagis, Christos D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.1}, URN = {urn:nbn:de:0030-drops-131371}, doi = {10.4230/OASIcs.ATMOS.2020.1}, annote = {Keywords: Algorithm Engineering, Route Planning, Public Transit, One-to-Many} }
Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Integrating ULTRA and Trip-Based Routing. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{sauer_et_al:OASIcs.ATMOS.2020.4, author = {Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias}, title = {{Integrating ULTRA and Trip-Based Routing}}, booktitle = {20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)}, pages = {4:1--4:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-170-2}, ISSN = {2190-6807}, year = {2020}, volume = {85}, editor = {Huisman, Dennis and Zaroliagis, Christos D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.4}, URN = {urn:nbn:de:0030-drops-131408}, doi = {10.4230/OASIcs.ATMOS.2020.4}, annote = {Keywords: Algorithms, Journey Planning, Multi-Modal, Public Transportation} }
Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Valentin Buchhold, Dorothea Wagner, Tim Zeitz, and Michael Zündorf. Customizable Contraction Hierarchies with Turn Costs. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{buchhold_et_al:OASIcs.ATMOS.2020.9, author = {Buchhold, Valentin and Wagner, Dorothea and Zeitz, Tim and Z\"{u}ndorf, Michael}, title = {{Customizable Contraction Hierarchies with Turn Costs}}, booktitle = {20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)}, pages = {9:1--9:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-170-2}, ISSN = {2190-6807}, year = {2020}, volume = {85}, editor = {Huisman, Dennis and Zaroliagis, Christos D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.9}, URN = {urn:nbn:de:0030-drops-131453}, doi = {10.4230/OASIcs.ATMOS.2020.9}, annote = {Keywords: Turn costs, realistic road networks, customizable contraction hierarchies, route planning, shortest paths} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Ben Strasser, Dorothea Wagner, and Tim Zeitz. Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 81:1-81:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{strasser_et_al:LIPIcs.ESA.2020.81, author = {Strasser, Ben and Wagner, Dorothea and Zeitz, Tim}, title = {{Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {81:1--81:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.81}, URN = {urn:nbn:de:0030-drops-129479}, doi = {10.4230/LIPIcs.ESA.2020.81}, annote = {Keywords: realistic road networks, time-dependent route planning, shortest paths} }
Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)
Lars Gottesbüren, Michael Hamann, Philipp Schoch, Ben Strasser, Dorothea Wagner, and Sven Zühlsdorf. Engineering Exact Quasi-Threshold Editing. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gottesburen_et_al:LIPIcs.SEA.2020.10, author = {Gottesb\"{u}ren, Lars and Hamann, Michael and Schoch, Philipp and Strasser, Ben and Wagner, Dorothea and Z\"{u}hlsdorf, Sven}, title = {{Engineering Exact Quasi-Threshold Editing}}, booktitle = {18th International Symposium on Experimental Algorithms (SEA 2020)}, pages = {10:1--10:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-148-1}, ISSN = {1868-8969}, year = {2020}, volume = {160}, editor = {Faro, Simone and Cantone, Domenico}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.10}, URN = {urn:nbn:de:0030-drops-120849}, doi = {10.4230/LIPIcs.SEA.2020.10}, annote = {Keywords: Edge Editing, Integer Linear Programming, FPT algorithm, Quasi-Threshold Editing} }
Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)
Lars Gottesbüren, Michael Hamann, Sebastian Schlag, and Dorothea Wagner. Advanced Flow-Based Multilevel Hypergraph Partitioning. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gottesburen_et_al:LIPIcs.SEA.2020.11, author = {Gottesb\"{u}ren, Lars and Hamann, Michael and Schlag, Sebastian and Wagner, Dorothea}, title = {{Advanced Flow-Based Multilevel Hypergraph Partitioning}}, booktitle = {18th International Symposium on Experimental Algorithms (SEA 2020)}, pages = {11:1--11:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-148-1}, ISSN = {1868-8969}, year = {2020}, volume = {160}, editor = {Faro, Simone and Cantone, Domenico}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.11}, URN = {urn:nbn:de:0030-drops-120859}, doi = {10.4230/LIPIcs.SEA.2020.11}, annote = {Keywords: Hypergraph Partitioning, Maximum Flows, Refinement} }
Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)
Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Faster Multi-Modal Route Planning With Bike Sharing Using ULTRA. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{sauer_et_al:LIPIcs.SEA.2020.16, author = {Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias}, title = {{Faster Multi-Modal Route Planning With Bike Sharing Using ULTRA}}, booktitle = {18th International Symposium on Experimental Algorithms (SEA 2020)}, pages = {16:1--16:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-148-1}, ISSN = {1868-8969}, year = {2020}, volume = {160}, editor = {Faro, Simone and Cantone, Domenico}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.16}, URN = {urn:nbn:de:0030-drops-120905}, doi = {10.4230/LIPIcs.SEA.2020.16}, annote = {Keywords: Algorithms, Route Planning, Bike Sharing, Public Transportation} }
Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)
Lukas Barth and Dorothea Wagner. Zipping Segment Trees. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{barth_et_al:LIPIcs.SEA.2020.25, author = {Barth, Lukas and Wagner, Dorothea}, title = {{Zipping Segment Trees}}, booktitle = {18th International Symposium on Experimental Algorithms (SEA 2020)}, pages = {25:1--25:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-148-1}, ISSN = {1868-8969}, year = {2020}, volume = {160}, editor = {Faro, Simone and Cantone, Domenico}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.25}, URN = {urn:nbn:de:0030-drops-120990}, doi = {10.4230/LIPIcs.SEA.2020.25}, annote = {Keywords: Segment Trees, Dynamic Segment Trees, Zip Trees, Data Structures} }