Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Kaito Harada, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa. A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 65:1-65:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{harada_et_al:LIPIcs.ESA.2024.65, author = {Harada, Kaito and Kitamura, Naoki and Izumi, Taisuke and Masuzawa, Toshimitsu}, title = {{A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {65:1--65: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.65}, URN = {urn:nbn:de:0030-drops-211367}, doi = {10.4230/LIPIcs.ESA.2024.65}, annote = {Keywords: data structure, distance sensitivity oracle, replacement path problem, graph algorithm} }
Published in: LIPIcs, Volume 309, 15th International Conference on Interactive Theorem Proving (ITP 2024)
Samuel Gruetter, Thomas Bourgeat, and Adam Chlipala. Verifying Software Emulation of an Unsupported Hardware Instruction. In 15th International Conference on Interactive Theorem Proving (ITP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 309, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gruetter_et_al:LIPIcs.ITP.2024.17, author = {Gruetter, Samuel and Bourgeat, Thomas and Chlipala, Adam}, title = {{Verifying Software Emulation of an Unsupported Hardware Instruction}}, booktitle = {15th International Conference on Interactive Theorem Proving (ITP 2024)}, pages = {17:1--17:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-337-9}, ISSN = {1868-8969}, year = {2024}, volume = {309}, editor = {Bertot, Yves and Kutsia, Temur and Norrish, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2024.17}, URN = {urn:nbn:de:0030-drops-207452}, doi = {10.4230/LIPIcs.ITP.2024.17}, annote = {Keywords: Software verification, Software-hardware boundary, Coq} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Yong Gu and Hanlin Ren. Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 76:1-76:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{gu_et_al:LIPIcs.ICALP.2021.76, author = {Gu, Yong and Ren, Hanlin}, title = {{Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {76:1--76:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.76}, URN = {urn:nbn:de:0030-drops-141450}, doi = {10.4230/LIPIcs.ICALP.2021.76}, annote = {Keywords: graph theory, shortest paths, distance sensitivity oracles} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Hanlin Ren. Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{ren:LIPIcs.ESA.2020.79, author = {Ren, Hanlin}, title = {{Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {79:1--79:13}, 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.79}, URN = {urn:nbn:de:0030-drops-129450}, doi = {10.4230/LIPIcs.ESA.2020.79}, annote = {Keywords: Graph theory, Failure-prone structures} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Ruoxu Cen, Ran Duan, and Yong Gu. Roundtrip Spanners with (2k-1) Stretch. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 24:1-24:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cen_et_al:LIPIcs.ICALP.2020.24, author = {Cen, Ruoxu and Duan, Ran and Gu, Yong}, title = {{Roundtrip Spanners with (2k-1) Stretch}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {24:1--24:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.24}, URN = {urn:nbn:de:0030-drops-124313}, doi = {10.4230/LIPIcs.ICALP.2020.24}, annote = {Keywords: Graph theory, Deterministic algorithm, Roundtrip spanners} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Ran Duan, Yong Gu, and Le Zhang. Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{duan_et_al:LIPIcs.ICALP.2018.44, author = {Duan, Ran and Gu, Yong and Zhang, Le}, title = {{Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {44:1--44:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.44}, URN = {urn:nbn:de:0030-drops-90487}, doi = {10.4230/LIPIcs.ICALP.2018.44}, annote = {Keywords: Graph algorithms, Matrix multiplication, Non-decreasing paths} }
Feedback for Dagstuhl Publishing