Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Amir Abboud and Nathan Wallheimer. Worst-Case to Expander-Case Reductions: Derandomized and Generalized. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abboud_et_al:LIPIcs.ESA.2024.4, author = {Abboud, Amir and Wallheimer, Nathan}, title = {{Worst-Case to Expander-Case Reductions: Derandomized and Generalized}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {4:1--4: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.4}, URN = {urn:nbn:de:0030-drops-210751}, doi = {10.4230/LIPIcs.ESA.2024.4}, annote = {Keywords: Fine-grained complexity, expander graphs, self-reductions, worst-case to expander-case, expander decomposition, dynamic algorithms, exact and parameterized complexity, max-cut, maximum matching, k-clique detection, densest subgraph} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Lars Gottesbüren, Nikos Parotsidis, and Maximilian Probst Gutenberg. Practical Expander Decomposition. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 61:1-61:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gottesburen_et_al:LIPIcs.ESA.2024.61, author = {Gottesb\"{u}ren, Lars and Parotsidis, Nikos and Gutenberg, Maximilian Probst}, title = {{Practical Expander Decomposition}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {61:1--61:17}, 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.61}, URN = {urn:nbn:de:0030-drops-211323}, doi = {10.4230/LIPIcs.ESA.2024.61}, annote = {Keywords: Expander Decomposition, Clustering, Graph Algorithms} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Dani Dorfman, Haim Kaplan, Robert E. Tarjan, and Uri Zwick. Optimal Energetic Paths for Electric Cars. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dorfman_et_al:LIPIcs.ESA.2023.42, author = {Dorfman, Dani and Kaplan, Haim and Tarjan, Robert E. and Zwick, Uri}, title = {{Optimal Energetic Paths for Electric Cars}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {42:1--42:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.42}, URN = {urn:nbn:de:0030-drops-186955}, doi = {10.4230/LIPIcs.ESA.2023.42}, annote = {Keywords: Electric cars, Optimal Paths, Battery depletion} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Daniel Agassy, Dani Dorfman, and Haim Kaplan. Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{agassy_et_al:LIPIcs.ICALP.2023.9, author = {Agassy, Daniel and Dorfman, Dani and Kaplan, Haim}, title = {{Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {9:1--9:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.9}, URN = {urn:nbn:de:0030-drops-180619}, doi = {10.4230/LIPIcs.ICALP.2023.9}, annote = {Keywords: Exapander Decomposition, Cut-Matching Game} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Dani Dorfman, Haim Kaplan, and Uri Zwick. A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 114:1-114:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dorfman_et_al:LIPIcs.ICALP.2019.114, author = {Dorfman, Dani and Kaplan, Haim and Zwick, Uri}, title = {{A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {114:1--114:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.114}, URN = {urn:nbn:de:0030-drops-106909}, doi = {10.4230/LIPIcs.ICALP.2019.114}, annote = {Keywords: Energy Games, Mean Payoff Games, Scaling} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Dani Dorfman, Haim Kaplan, László Kozma, and Uri Zwick. Pairing heaps: the forward variant. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dorfman_et_al:LIPIcs.MFCS.2018.13, author = {Dorfman, Dani and Kaplan, Haim and Kozma, L\'{a}szl\'{o} and Zwick, Uri}, title = {{Pairing heaps: the forward variant}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {13:1--13:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul 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.MFCS.2018.13}, URN = {urn:nbn:de:0030-drops-95956}, doi = {10.4230/LIPIcs.MFCS.2018.13}, annote = {Keywords: data structure, priority queue, pairing heap} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Dani Dorfman, Haim Kaplan, László Kozma, Seth Pettie, and Uri Zwick. Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dorfman_et_al:LIPIcs.ESA.2018.24, author = {Dorfman, Dani and Kaplan, Haim and Kozma, L\'{a}szl\'{o} and Pettie, Seth and Zwick, Uri}, title = {{Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {24:1--24:13}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.24}, URN = {urn:nbn:de:0030-drops-94879}, doi = {10.4230/LIPIcs.ESA.2018.24}, annote = {Keywords: data structure, priority queue, pairing heap, binary search tree} }
Feedback for Dagstuhl Publishing