Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Rubi Arviv, Lily Chung, Reut Levi, and Edward Pyne. Improved Local Computation Algorithms for Constructing Spanners. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arviv_et_al:LIPIcs.APPROX/RANDOM.2023.42, author = {Arviv, Rubi and Chung, Lily and Levi, Reut and Pyne, Edward}, title = {{Improved Local Computation Algorithms for Constructing Spanners}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {42:1--42:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.42}, URN = {urn:nbn:de:0030-drops-188671}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.42}, annote = {Keywords: Local Computation Algorithms, Spanners} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Noy Biton, Reut Levi, and Moti Medina. Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{biton_et_al:LIPIcs.MFCS.2023.19, author = {Biton, Noy and Levi, Reut and Medina, Moti}, title = {{Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {19:1--19:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.19}, URN = {urn:nbn:de:0030-drops-185534}, doi = {10.4230/LIPIcs.MFCS.2023.19}, annote = {Keywords: the CONGEST model, Hamiltonian Path, Hamiltonian Cycle, Dirac graphs, Ore graphs, graph-algorithms} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Reut Levi and Nadav Shoshan. Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{levi_et_al:LIPIcs.APPROX/RANDOM.2021.61, author = {Levi, Reut and Shoshan, Nadav}, title = {{Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {61:1--61:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.61}, URN = {urn:nbn:de:0030-drops-147540}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.61}, annote = {Keywords: Property Testing, Hamiltonian path, minor free graphs, sparse spanning sub-graphs} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Reut Levi. Testing Triangle Freeness in the General Model in Graphs with Arboricity O(√n). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 93:1-93:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{levi:LIPIcs.ICALP.2021.93, author = {Levi, Reut}, title = {{Testing Triangle Freeness in the General Model in Graphs with Arboricity O(√n)}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {93:1--93:13}, 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.93}, URN = {urn:nbn:de:0030-drops-141626}, doi = {10.4230/LIPIcs.ICALP.2021.93}, annote = {Keywords: Property Testing, Triangle-Freeness} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Reut Levi and Moti Medina. Distributed Testing of Graph Isomorphism in the CONGEST Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{levi_et_al:LIPIcs.APPROX/RANDOM.2020.19, author = {Levi, Reut and Medina, Moti}, title = {{Distributed Testing of Graph Isomorphism in the CONGEST Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {19:1--19:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.19}, URN = {urn:nbn:de:0030-drops-126221}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.19}, annote = {Keywords: the CONGEST model, graph isomorphism, distributed property testing, distributed decision, graph algorithms} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Hendrik Fichtenberger, Reut Levi, Yadu Vasudev, and Maximilian Wötzel. A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fichtenberger_et_al:LIPIcs.ICALP.2018.52, author = {Fichtenberger, Hendrik and Levi, Reut and Vasudev, Yadu and W\"{o}tzel, Maximilian}, title = {{A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {52:1--52: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.52}, URN = {urn:nbn:de:0030-drops-90563}, doi = {10.4230/LIPIcs.ICALP.2018.52}, annote = {Keywords: graph property testing, minor-free graphs} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Christoph Lenzen and Reut Levi. A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 87:1-87:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{lenzen_et_al:LIPIcs.ICALP.2018.87, author = {Lenzen, Christoph and Levi, Reut}, title = {{A Centralized Local Algorithm for the Sparse Spanning Graph Problem}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {87:1--87: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.87}, URN = {urn:nbn:de:0030-drops-90919}, doi = {10.4230/LIPIcs.ICALP.2018.87}, annote = {Keywords: local, spanning graph, sparse} }
Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)
Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three Notes on Distributed Property Testing. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 15:1-15:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{even_et_al:LIPIcs.DISC.2017.15, author = {Even, Guy and Fischer, Orr and Fraigniaud, Pierre and Gonen, Tzlil and Levi, Reut and Medina, Moti and Montealegre, Pedro and Olivetti, Dennis and Oshman, Rotem and Rapaport, Ivan and Todinca, Ioan}, title = {{Three Notes on Distributed Property Testing}}, booktitle = {31st International Symposium on Distributed Computing (DISC 2017)}, pages = {15:1--15:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-053-8}, ISSN = {1868-8969}, year = {2017}, volume = {91}, editor = {Richa, Andr\'{e}a}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.15}, URN = {urn:nbn:de:0030-drops-79847}, doi = {10.4230/LIPIcs.DISC.2017.15}, annote = {Keywords: Property testing, Property correcting, Distributed algorithms, CONGEST model} }
Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)
Christoph Lenzen and Reut Levi. Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 57:1-57:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{lenzen_et_al:LIPIcs.DISC.2017.57, author = {Lenzen, Christoph and Levi, Reut}, title = {{Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem}}, booktitle = {31st International Symposium on Distributed Computing (DISC 2017)}, pages = {57:1--57:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-053-8}, ISSN = {1868-8969}, year = {2017}, volume = {91}, editor = {Richa, Andr\'{e}a}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.57}, URN = {urn:nbn:de:0030-drops-80064}, doi = {10.4230/LIPIcs.DISC.2017.57}, annote = {Keywords: local, spanning graph, sparse} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Guy Even, Reut Levi, Moti Medina, and Adi Rosén. Sublinear Random Access Generators for Preferential Attachment Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{even_et_al:LIPIcs.ICALP.2017.6, author = {Even, Guy and Levi, Reut and Medina, Moti and Ros\'{e}n, Adi}, title = {{Sublinear Random Access Generators for Preferential Attachment Graphs}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {6:1--6:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.6}, URN = {urn:nbn:de:0030-drops-74242}, doi = {10.4230/LIPIcs.ICALP.2017.6}, annote = {Keywords: local computation algorithms, preferential attachment graphs, random recursive trees, sublinear algorithms} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Reut Levi, Dana Ron, and Ronitt Rubinfeld. A Local Algorithm for Constructing Spanners in Minor-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{levi_et_al:LIPIcs.APPROX-RANDOM.2016.38, author = {Levi, Reut and Ron, Dana and Rubinfeld, Ronitt}, title = {{A Local Algorithm for Constructing Spanners in Minor-Free Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {38:1--38:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.38}, URN = {urn:nbn:de:0030-drops-66613}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.38}, annote = {Keywords: spanners, sparse subgraphs, local algorithms, excluded-minor} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local Algorithms for Sparse Spanning Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 826-842, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{levi_et_al:LIPIcs.APPROX-RANDOM.2014.826, author = {Levi, Reut and Ron, Dana and Rubinfeld, Ronitt}, title = {{Local Algorithms for Sparse Spanning Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {826--842}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.826}, URN = {urn:nbn:de:0030-drops-47410}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.826}, annote = {Keywords: local, spanning graph, sparse} }
Feedback for Dagstuhl Publishing