Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan. Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{deligkas_et_al:LIPIcs.ICALP.2024.53, author = {Deligkas, Argyrios and Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ramanujan, M. S.}, title = {{Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {53:1--53: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.53}, URN = {urn:nbn:de:0030-drops-201968}, doi = {10.4230/LIPIcs.ICALP.2024.53}, annote = {Keywords: coordinated motion planning, multi-agent path finding, parameterized complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Andreas Björklund, Petteri Kaski, and Jesper Nederlof. Another Hamiltonian Cycle in Bipartite Pfaffian Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2024.26, author = {Bj\"{o}rklund, Andreas and Kaski, Petteri and Nederlof, Jesper}, title = {{Another Hamiltonian Cycle in Bipartite Pfaffian Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {26:1--26: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.26}, URN = {urn:nbn:de:0030-drops-201692}, doi = {10.4230/LIPIcs.ICALP.2024.26}, annote = {Keywords: Another Hamiltonian cycle, Pfaffian graph, planar graph, Thomason’s lollipop method} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Ishay Haviv. The Chromatic Number of Kneser Hypergraphs via Consensus Division. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{haviv:LIPIcs.ITCS.2024.60, author = {Haviv, Ishay}, title = {{The Chromatic Number of Kneser Hypergraphs via Consensus Division}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {60:1--60:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.60}, URN = {urn:nbn:de:0030-drops-195883}, doi = {10.4230/LIPIcs.ITCS.2024.60}, annote = {Keywords: Kneser hypergraphs, consensus division, the complexity classes PPA-p} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Argyrios Deligkas, Michail Fasoulakis, and Evangelos Markakis. A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{deligkas_et_al:LIPIcs.ESA.2022.41, author = {Deligkas, Argyrios and Fasoulakis, Michail and Markakis, Evangelos}, title = {{A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {41:1--41:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.41}, URN = {urn:nbn:de:0030-drops-169790}, doi = {10.4230/LIPIcs.ESA.2022.41}, annote = {Keywords: bimatrix games, approximate Nash equilibria} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, and Igor Potapov. The Complexity of Periodic Energy Minimisation. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{adamson_et_al:LIPIcs.MFCS.2022.8, author = {Adamson, Duncan and Deligkas, Argyrios and Gusev, Vladimir V. and Potapov, Igor}, title = {{The Complexity of Periodic Energy Minimisation}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {8:1--8:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.8}, URN = {urn:nbn:de:0030-drops-168065}, doi = {10.4230/LIPIcs.MFCS.2022.8}, annote = {Keywords: Optimisation of periodic structures, tiling, undecidability, NP-hardness} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Duncan Adamson, Vladimir V. Gusev, Igor Potapov, and Argyrios Deligkas. Ranking Bracelets in Polynomial Time. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{adamson_et_al:LIPIcs.CPM.2021.4, author = {Adamson, Duncan and Gusev, Vladimir V. and Potapov, Igor and Deligkas, Argyrios}, title = {{Ranking Bracelets in Polynomial Time}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {4:1--4:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.4}, URN = {urn:nbn:de:0030-drops-139554}, doi = {10.4230/LIPIcs.CPM.2021.4}, annote = {Keywords: Bracelets, Ranking, Necklaces} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{deligkas_et_al:LIPIcs.MFCS.2020.27, author = {Deligkas, Argyrios and Mertzios, George B. and Spirakis, Paul G. and Zamaraev, Viktor}, title = {{Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {27:1--27:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.27}, URN = {urn:nbn:de:0030-drops-126953}, doi = {10.4230/LIPIcs.MFCS.2020.27}, annote = {Keywords: Hamiltonian cycle, cubic graph, exact algorithm, approximation algorithm} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Argyrios Deligkas, John Fearnley, and Rahul Savani. Tree Polymatrix Games Are PPAD-Hard. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{deligkas_et_al:LIPIcs.ICALP.2020.38, author = {Deligkas, Argyrios and Fearnley, John and Savani, Rahul}, title = {{Tree Polymatrix Games Are PPAD-Hard}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {38:1--38:14}, 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.38}, URN = {urn:nbn:de:0030-drops-124458}, doi = {10.4230/LIPIcs.ICALP.2020.38}, annote = {Keywords: Nash Equilibria, Polymatrix Games, PPAD, Brouwer Fixed Points} }
Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)
Dmytro Antypov, Argyrios Deligkas, Vladimir Gusev, Matthew J. Rosseinsky, Paul G. Spirakis, and Michail Theofilatos. Crystal Structure Prediction via Oblivious Local Search. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{antypov_et_al:LIPIcs.SEA.2020.21, author = {Antypov, Dmytro and Deligkas, Argyrios and Gusev, Vladimir and Rosseinsky, Matthew J. and Spirakis, Paul G. and Theofilatos, Michail}, title = {{Crystal Structure Prediction via Oblivious Local Search}}, booktitle = {18th International Symposium on Experimental Algorithms (SEA 2020)}, pages = {21:1--21: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.21}, URN = {urn:nbn:de:0030-drops-120950}, doi = {10.4230/LIPIcs.SEA.2020.21}, annote = {Keywords: crystal structure prediction, local search, combinatorial neighborhood} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 138:1-138:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{deligkas_et_al:LIPIcs.ICALP.2019.138, author = {Deligkas, Argyrios and Fearnley, John and Melissourgos, Themistoklis and Spirakis, Paul G.}, title = {{Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {138:1--138: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.138}, URN = {urn:nbn:de:0030-drops-107141}, doi = {10.4230/LIPIcs.ICALP.2019.138}, annote = {Keywords: PPA, FIXP, ETR, consensus halving, circuit, reduction, complexity class} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Argyrios Deligkas and Reshef Meir. Directed Graph Minors and Serial-Parallel Width. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{deligkas_et_al:LIPIcs.MFCS.2018.44, author = {Deligkas, Argyrios and Meir, Reshef}, title = {{Directed Graph Minors and Serial-Parallel Width}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {44:1--44: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.44}, URN = {urn:nbn:de:0030-drops-96261}, doi = {10.4230/LIPIcs.MFCS.2018.44}, annote = {Keywords: directed minors, pathwidth} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Argyrios Deligkas, George B. Mertzios, and Paul G. Spirakis. Binary Search in Graphs Revisited. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{deligkas_et_al:LIPIcs.MFCS.2017.20, author = {Deligkas, Argyrios and Mertzios, George B. and Spirakis, Paul G.}, title = {{Binary Search in Graphs Revisited}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.20}, URN = {urn:nbn:de:0030-drops-80589}, doi = {10.4230/LIPIcs.MFCS.2017.20}, annote = {Keywords: binary search, graph, approximate query, probabilistic algorithm, lower bound.} }