Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Ofer Neiman and Idan Shabat. On the Size Overhead of Pairwise Spanners. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 83:1-83:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{neiman_et_al:LIPIcs.ITCS.2024.83, author = {Neiman, Ofer and Shabat, Idan}, title = {{On the Size Overhead of Pairwise Spanners}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {83:1--83: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.83}, URN = {urn:nbn:de:0030-drops-196110}, doi = {10.4230/LIPIcs.ITCS.2024.83}, annote = {Keywords: Graph Algorithms, Shortest Paths, Spanners} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Ofer Neiman and Idan Shabat. A Unified Framework for Hopsets. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{neiman_et_al:LIPIcs.ESA.2022.81, author = {Neiman, Ofer and Shabat, Idan}, title = {{A Unified Framework for Hopsets}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {81:1--81:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.81}, URN = {urn:nbn:de:0030-drops-170192}, doi = {10.4230/LIPIcs.ESA.2022.81}, annote = {Keywords: Graph Algorithms, Shortest Paths, Hopsets} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Almost Shortest Paths with Near-Additive Error in Weighted Graphs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{elkin_et_al:LIPIcs.SWAT.2022.23, author = {Elkin, Michael and Gitlitz, Yuval and Neiman, Ofer}, title = {{Almost Shortest Paths with Near-Additive Error in Weighted Graphs}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {23:1--23:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.23}, URN = {urn:nbn:de:0030-drops-161833}, doi = {10.4230/LIPIcs.SWAT.2022.23}, annote = {Keywords: spanners, hopset, shortest paths, PRAM, distance oracles} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Michael Elkin and Ofer Neiman. Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 27:1-27:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{elkin_et_al:LIPIcs.STACS.2022.27, author = {Elkin, Michael and Neiman, Ofer}, title = {{Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {27:1--27:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.27}, URN = {urn:nbn:de:0030-drops-158379}, doi = {10.4230/LIPIcs.STACS.2022.27}, annote = {Keywords: Shortest paths, matrix multiplication, hopsets} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Improved Weighted Additive Spanners. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{elkin_et_al:LIPIcs.DISC.2021.21, author = {Elkin, Michael and Gitlitz, Yuval and Neiman, Ofer}, title = {{Improved Weighted Additive Spanners}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {21:1--21:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.21}, URN = {urn:nbn:de:0030-drops-148232}, doi = {10.4230/LIPIcs.DISC.2021.21}, annote = {Keywords: Graph theory, Pure additive spanners} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Hung Le and Shay Solomon. Light Euclidean Spanners with Steiner Points. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 67:1-67:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{le_et_al:LIPIcs.ESA.2020.67, author = {Le, Hung and Solomon, Shay}, title = {{Light Euclidean Spanners with Steiner Points}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {67:1--67:22}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.67}, URN = {urn:nbn:de:0030-drops-129331}, doi = {10.4230/LIPIcs.ESA.2020.67}, annote = {Keywords: Euclidean spanners, Steiner spanners, light spanners} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Arnold Filtser. Scattering and Sparse Partitions, and Their Applications. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 47:1-47:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{filtser:LIPIcs.ICALP.2020.47, author = {Filtser, Arnold}, title = {{Scattering and Sparse Partitions, and Their Applications}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {47:1--47:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.47}, URN = {urn:nbn:de:0030-drops-124547}, doi = {10.4230/LIPIcs.ICALP.2020.47}, annote = {Keywords: Scattering partitions, sparse partitions, sparse covers, Steiner point removal, Universal Steiner tree, Universal TSP} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Arnold Filtser. On Strong Diameter Padded Decompositions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{filtser:LIPIcs.APPROX-RANDOM.2019.6, author = {Filtser, Arnold}, title = {{On Strong Diameter Padded Decompositions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {6:1--6:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.6}, URN = {urn:nbn:de:0030-drops-112217}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.6}, annote = {Keywords: Padded decomposition, Strong Diameter, Sparse Cover, Doubling Dimension, Minor free graphs, Unique Games, Spanners, Distance Oracles} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, and Christian Wulff-Nilsen. Constructing Light Spanners Deterministically in Near-Linear Time. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{alstrup_et_al:LIPIcs.ESA.2019.4, author = {Alstrup, Stephen and Dahlgaard, S{\o}ren and Filtser, Arnold and St\"{o}ckel, Morten and Wulff-Nilsen, Christian}, title = {{Constructing Light Spanners Deterministically in Near-Linear Time}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {4:1--4:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.4}, URN = {urn:nbn:de:0030-drops-111255}, doi = {10.4230/LIPIcs.ESA.2019.4}, annote = {Keywords: Spanners, Light Spanners, Efficient Construction, Deterministic Dynamic Distance Oracle} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Yair Bartal, Nova Fandina, and Ofer Neiman. Covering Metric Spaces by Few Trees. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bartal_et_al:LIPIcs.ICALP.2019.20, author = {Bartal, Yair and Fandina, Nova and Neiman, Ofer}, title = {{Covering Metric Spaces by Few Trees}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {20:1--20:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.20}, URN = {urn:nbn:de:0030-drops-105967}, doi = {10.4230/LIPIcs.ICALP.2019.20}, annote = {Keywords: tree cover, Ramsey tree cover, probabilistic hierarchical family} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Arnold Filtser and Ofer Neiman. Light Spanners for High Dimensional Norms via Stochastic Decompositions. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{filtser_et_al:LIPIcs.ESA.2018.29, author = {Filtser, Arnold and Neiman, Ofer}, title = {{Light Spanners for High Dimensional Norms via Stochastic Decompositions}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {29:1--29: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.29}, URN = {urn:nbn:de:0030-drops-94922}, doi = {10.4230/LIPIcs.ESA.2018.29}, annote = {Keywords: Spanners, Stochastic Decompositions, High Dimensional Euclidean Space, Doubling Dimension, Genus Graphs} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Michael Elkin and Ofer Neiman. Near Isometric Terminal Embeddings for Doubling Metrics. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{elkin_et_al:LIPIcs.SoCG.2018.36, author = {Elkin, Michael and Neiman, Ofer}, title = {{Near Isometric Terminal Embeddings for Doubling Metrics}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {36:1--36:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.36}, URN = {urn:nbn:de:0030-drops-87498}, doi = {10.4230/LIPIcs.SoCG.2018.36}, annote = {Keywords: metric embedding, spanners, doubling metrics} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Alexandr Andoni, Assaf Naor, and Ofer Neiman. Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{andoni_et_al:LIPIcs.ICALP.2016.83, author = {Andoni, Alexandr and Naor, Assaf and Neiman, Ofer}, title = {{Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {83:1--83: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.83}, URN = {urn:nbn:de:0030-drops-62028}, doi = {10.4230/LIPIcs.ICALP.2016.83}, annote = {Keywords: Transportation metric, embedding, snowflake, sketching} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 242-264, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{elkin_et_al:LIPIcs.APPROX-RANDOM.2015.242, author = {Elkin, Michael and Filtser, Arnold and Neiman, Ofer}, title = {{Terminal Embeddings}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {242--264}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.242}, URN = {urn:nbn:de:0030-drops-53064}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.242}, annote = {Keywords: embedding, distortion, terminals} }
Feedback for Dagstuhl Publishing