Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
Diego Arroyuelo and Juan Pablo Castillo. Trie-Compressed Adaptive Set Intersection. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arroyuelo_et_al:LIPIcs.CPM.2023.1, author = {Arroyuelo, Diego and Castillo, Juan Pablo}, title = {{Trie-Compressed Adaptive Set Intersection}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {1:1--1:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-276-1}, ISSN = {1868-8969}, year = {2023}, volume = {259}, editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.1}, URN = {urn:nbn:de:0030-drops-179552}, doi = {10.4230/LIPIcs.CPM.2023.1}, annote = {Keywords: Set intersection problem, Adaptive Algorithms, Compressed and compact data structures} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Daniel Lokshtanov and Bernardo Subercaseaux. Wordle Is NP-Hard. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 19:1-19:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lokshtanov_et_al:LIPIcs.FUN.2022.19, author = {Lokshtanov, Daniel and Subercaseaux, Bernardo}, title = {{Wordle Is NP-Hard}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {19:1--19:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.19}, URN = {urn:nbn:de:0030-drops-159893}, doi = {10.4230/LIPIcs.FUN.2022.19}, annote = {Keywords: wordle, np-hardness, complexity} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Jean Cardinal, Justin Dallant, and John Iacono. An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.24, author = {Cardinal, Jean and Dallant, Justin and Iacono, John}, title = {{An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.24}, URN = {urn:nbn:de:0030-drops-146057}, doi = {10.4230/LIPIcs.ESA.2021.24}, annote = {Keywords: computational geometry, instance-optimality, colored point sets, empty rectangles, visibility} }
Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)
Jérémy Barbay and Bernardo Subercaseaux. The Computational Complexity of Evil Hangman. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 23:1-23:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{barbay_et_al:LIPIcs.FUN.2021.23, author = {Barbay, J\'{e}r\'{e}my and Subercaseaux, Bernardo}, title = {{The Computational Complexity of Evil Hangman}}, booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)}, pages = {23:1--23:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-145-0}, ISSN = {1868-8969}, year = {2020}, volume = {157}, editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.23}, URN = {urn:nbn:de:0030-drops-127840}, doi = {10.4230/LIPIcs.FUN.2021.23}, annote = {Keywords: combinatorial game theory, computational complexity, decidability, hangman} }
Published in: Dagstuhl Reports, Volume 8, Issue 7 (2019)
Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti. Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281). In Dagstuhl Reports, Volume 8, Issue 7, pp. 44-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{barbay_et_al:DagRep.8.7.44, author = {Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao}, title = {{Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281)}}, pages = {44--61}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {8}, number = {7}, editor = {Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.8.7.44}, URN = {urn:nbn:de:0030-drops-101724}, doi = {10.4230/DagRep.8.7.44}, annote = {Keywords: adaptive (analysis of) algorithms, compressed data structures, compressed indices, parameterized complexity} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
J. Ian Munro and Sebastian Wild. Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{munro_et_al:LIPIcs.ESA.2018.63, author = {Munro, J. Ian and Wild, Sebastian}, title = {{Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {63:1--63:16}, 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.63}, URN = {urn:nbn:de:0030-drops-95265}, doi = {10.4230/LIPIcs.ESA.2018.63}, annote = {Keywords: adaptive sorting, nearly-optimal binary search trees, Timsort} }
Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti. Synergistic Solutions on MultiSets. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{barbay_et_al:LIPIcs.CPM.2017.31, author = {Barbay, J\'{e}r\'{e}my and Ochoa, Carlos and Satti, Srinivasa Rao}, title = {{Synergistic Solutions on MultiSets}}, booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)}, pages = {31:1--31:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-039-2}, ISSN = {1868-8969}, year = {2017}, volume = {78}, editor = {K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.31}, URN = {urn:nbn:de:0030-drops-73441}, doi = {10.4230/LIPIcs.CPM.2017.31}, annote = {Keywords: deferred data structure, multivariate analysis, quick sort, select} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight Hardness Results for Maximum Weight Rectangles. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{backurs_et_al:LIPIcs.ICALP.2016.81, author = {Backurs, Arturs and Dikkala, Nishanth and Tzamos, Christos}, title = {{Tight Hardness Results for Maximum Weight Rectangles}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {81:1--81:13}, 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.81}, URN = {urn:nbn:de:0030-drops-62040}, doi = {10.4230/LIPIcs.ICALP.2016.81}, annote = {Keywords: Maximum Rectangles, Hardness in P} }
Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Jérémy Barbay. Optimal Prefix Free Codes with Partial Sorting. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{barbay:LIPIcs.CPM.2016.29, author = {Barbay, J\'{e}r\'{e}my}, title = {{Optimal Prefix Free Codes with Partial Sorting}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, pages = {29:1--29:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.29}, URN = {urn:nbn:de:0030-drops-60635}, doi = {10.4230/LIPIcs.CPM.2016.29}, annote = {Keywords: Deferred Data Structure, Huffman, Median, Optimal Prefix Free Codes, van Leeuwen.} }
Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)
Jérémy Barbay. Selenite Towers Move Faster Than Hanoï Towers, But Still Require Exponential Time. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{barbay:LIPIcs.FUN.2016.5, author = {Barbay, J\'{e}r\'{e}my}, title = {{Selenite Towers Move Faster Than Hano\"{i} Towers, But Still Require Exponential Time}}, booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-005-7}, ISSN = {1868-8969}, year = {2016}, volume = {49}, editor = {Demaine, Erik D. and Grandoni, Fabrizio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.5}, URN = {urn:nbn:de:0030-drops-58729}, doi = {10.4230/LIPIcs.FUN.2016.5}, annote = {Keywords: Br\"{a}hma tower, Disk Pile, Hanoi Tower, Levitating Tower, Recursivity} }
Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)
Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{barbay_et_al:DagSemProc.09171.1, author = {Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf}, title = {{09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms}}, booktitle = {Adaptive, Output Sensitive, Online and Parameterized Algorithms}, pages = {1--11}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9171}, editor = {J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.1}, URN = {urn:nbn:de:0030-drops-21228}, doi = {10.4230/DagSemProc.09171.1}, annote = {Keywords: Adaptive analysis, instance optimal algoritms, fixed parameter tractable, output sensitive algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)
Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{barbay_et_al:DagSemProc.09171.2, author = {Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf}, title = {{09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms}}, booktitle = {Adaptive, Output Sensitive, Online and Parameterized Algorithms}, pages = {1--1}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9171}, editor = {J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.2}, URN = {urn:nbn:de:0030-drops-21207}, doi = {10.4230/DagSemProc.09171.2}, annote = {Keywords: Adaptive analysis, instance optimal algorithms, fixed parameter tractable, output sensitive algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)
Spyros Angelopoulos. Parameterized Analysis of Online Steiner Tree Problems. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{angelopoulos:DagSemProc.09171.3, author = {Angelopoulos, Spyros}, title = {{Parameterized Analysis of Online Steiner Tree Problems}}, booktitle = {Adaptive, Output Sensitive, Online and Parameterized Algorithms}, pages = {1--11}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9171}, editor = {J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.3}, URN = {urn:nbn:de:0030-drops-21210}, doi = {10.4230/DagSemProc.09171.3}, annote = {Keywords: Online algorithms, Steiner tree problems, adaptive and parameteried analysis} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Jeremy Barbay and Gonzalo Navarro. Compressed Representations of Permutations, and Applications. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 111-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{barbay_et_al:LIPIcs.STACS.2009.1814, author = {Barbay, Jeremy and Navarro, Gonzalo}, title = {{Compressed Representations of Permutations, and Applications}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {111--122}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1814}, URN = {urn:nbn:de:0030-drops-18148}, doi = {10.4230/LIPIcs.STACS.2009.1814}, annote = {Keywords: Compression, Permutations, Succinct data structures, Adaptive sorting} }
Feedback for Dagstuhl Publishing