OASIcs, Volume 11
CCA 2009, August 18-22, 2009, Ljubljana, Slovenia
Editors: Andrej Bauer, Peter Hertling, and Ker-I Ko
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Duncan Adamson, Pamela Fleischmann, Annika Huch, Tore Koß, Florin Manea, and Dirk Nowotka. k-Universality of Regular Languages. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{adamson_et_al:LIPIcs.ISAAC.2023.4, author = {Adamson, Duncan and Fleischmann, Pamela and Huch, Annika and Ko{\ss}, Tore and Manea, Florin and Nowotka, Dirk}, title = {{k-Universality of Regular Languages}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {4:1--4:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.4}, URN = {urn:nbn:de:0030-drops-193064}, doi = {10.4230/LIPIcs.ISAAC.2023.4}, annote = {Keywords: String Algorithms, Regular Languages, Finite Automata, Subsequences} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Jana Holznigenkemper, Christian Komusiewicz, Nils Morawietz, and Bernhard Seeger. On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{holznigenkemper_et_al:LIPIcs.MFCS.2023.54, author = {Holznigenkemper, Jana and Komusiewicz, Christian and Morawietz, Nils and Seeger, Bernhard}, title = {{On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {54:1--54:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.54}, URN = {urn:nbn:de:0030-drops-185889}, doi = {10.4230/LIPIcs.MFCS.2023.54}, annote = {Keywords: Parameterized Complexity, Median String, Time Series, ETH} }
Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
Christian Komusiewicz, Simone Linz, Nils Morawietz, and Jannik Schestag. On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{komusiewicz_et_al:LIPIcs.CPM.2023.18, author = {Komusiewicz, Christian and Linz, Simone and Morawietz, Nils and Schestag, Jannik}, title = {{On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {18:1--18:18}, 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.18}, URN = {urn:nbn:de:0030-drops-179729}, doi = {10.4230/LIPIcs.CPM.2023.18}, annote = {Keywords: phylogenetic trees, parameterized complexity, tree distances, NNI, TBR} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček, Alon Rosen, and Nikolaj I. Schwartzbach. PPP-Completeness and Extremal Combinatorics. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bourneuf_et_al:LIPIcs.ITCS.2023.22, author = {Bourneuf, Romain and Folwarczn\'{y}, Luk\'{a}\v{s} and Hub\'{a}\v{c}ek, Pavel and Rosen, Alon and Schwartzbach, Nikolaj I.}, title = {{PPP-Completeness and Extremal Combinatorics}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {22:1--22:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.22}, URN = {urn:nbn:de:0030-drops-175255}, doi = {10.4230/LIPIcs.ITCS.2023.22}, annote = {Keywords: total search problems, extremal combinatorics, PPP-completeness} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, and Marek Sokołowski. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 93:1-93:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{majewski_et_al:LIPIcs.ICALP.2022.93, author = {Majewski, Konrad and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana and Okrasa, Karolina and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Soko{\l}owski, Marek}, title = {{Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gy\'{a}rf\'{a}s' Path Argument}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {93:1--93:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.93}, URN = {urn:nbn:de:0030-drops-164343}, doi = {10.4230/LIPIcs.ICALP.2022.93}, annote = {Keywords: Max Independent Set, subdivided claw, QPTAS, subexponential-time algorithm} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Benjamin Aram Berendsohn. The Diameter of Caterpillar Associahedra. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{berendsohn:LIPIcs.SWAT.2022.14, author = {Berendsohn, Benjamin Aram}, title = {{The Diameter of Caterpillar Associahedra}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {14:1--14:12}, 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.14}, URN = {urn:nbn:de:0030-drops-161743}, doi = {10.4230/LIPIcs.SWAT.2022.14}, annote = {Keywords: Graph Associahedra, Binary Search Trees, Elimination Trees} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Pavel Dvořák and Bruno Loff. Lower Bounds for Semi-adaptive Data Structures via Corruption. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dvorak_et_al:LIPIcs.FSTTCS.2020.20, author = {Dvo\v{r}\'{a}k, Pavel and Loff, Bruno}, title = {{Lower Bounds for Semi-adaptive Data Structures via Corruption}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {20:1--20:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.20}, URN = {urn:nbn:de:0030-drops-132617}, doi = {10.4230/LIPIcs.FSTTCS.2020.20}, annote = {Keywords: semi-adaptive dynamic data structure, polynomial lower bound, corruption bound, information theory} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer. Colored Cut Games. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{morawietz_et_al:LIPIcs.FSTTCS.2020.30, author = {Morawietz, Nils and Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Sommer, Frank}, title = {{Colored Cut Games}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {30:1--30:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.30}, URN = {urn:nbn:de:0030-drops-132719}, doi = {10.4230/LIPIcs.FSTTCS.2020.30}, annote = {Keywords: Labeled Cut, Labeled Path, Network Robustness, Kernelization, PSPACE, Polynomial Hierarchy} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, and Xiaoming Sun. From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 8:1-8:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bei_et_al:LIPIcs.ITCS.2020.8, author = {Bei, Xiaohui and Chen, Shiteng and Guan, Ji and Qiao, Youming and Sun, Xiaoming}, title = {{From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {8:1--8:48}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.8}, URN = {urn:nbn:de:0030-drops-116932}, doi = {10.4230/LIPIcs.ITCS.2020.8}, annote = {Keywords: independent set, vertex coloring, graphs, matrix spaces, isotropic subspace} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Mark Braverman and Young Kun Ko. Semi-Direct Sum Theorem and Nearest Neighbor under l_infty. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{braverman_et_al:LIPIcs.APPROX-RANDOM.2018.6, author = {Braverman, Mark and Ko, Young Kun}, title = {{Semi-Direct Sum Theorem and Nearest Neighbor under l\underlineinfty}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {6:1--6:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, 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.2018.6}, URN = {urn:nbn:de:0030-drops-94101}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.6}, annote = {Keywords: Asymmetric Communication Lower Bound, Data Structure Lower Bound, Nearest Neighbor Search} }
Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)
6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@Proceedings{bauer_et_al:OASIcs.CCA.2009, title = {{OASIcs, Volume 11, CCA'09, Complete Volume}}, booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-12-5}, ISSN = {2190-6807}, year = {2012}, volume = {11}, editor = {Bauer, Andrej and Hertling, Peter and Ko, Ker-I}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009}, URN = {urn:nbn:de:0030-drops-35738}, doi = {10.4230/OASIcs.CCA.2009}, annote = {Keywords: Mathematics of Computing, Analysis of Algorithms and Problem Complexity} }
Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)
6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. i-ii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bauer_et_al:OASIcs.CCA.2009.2248, author = {Bauer, Andrej and Hertling, Peter and Ko, Ker-I}, title = {{CCA 2009 Front Matter - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis}}, booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)}, pages = {i--ii}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-12-5}, ISSN = {2190-6807}, year = {2009}, volume = {11}, editor = {Bauer, Andrej and Hertling, Peter and Ko, Ker-I}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2248}, URN = {urn:nbn:de:0030-drops-22486}, doi = {10.4230/OASIcs.CCA.2009.2248}, annote = {Keywords: Computable analysis, computability, complexity, Turing machine, constructive mathematics, real number computation, computer arithmetic, exact real ari} }
Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)
Andrej Bauer, Peter Hertling, and Ker-I Ko. CCA 2009 Preface - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bauer_et_al:OASIcs.CCA.2009.2249, author = {Bauer, Andrej and Hertling, Peter and Ko, Ker-I}, title = {{CCA 2009 Preface - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis}}, booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)}, pages = {1--1}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-12-5}, ISSN = {2190-6807}, year = {2009}, volume = {11}, editor = {Bauer, Andrej and Hertling, Peter and Ko, Ker-I}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2249}, URN = {urn:nbn:de:0030-drops-22492}, doi = {10.4230/OASIcs.CCA.2009.2249}, annote = {Keywords: Computable analysis, computability, complexity, Turing machine, constructive mathematics, real number computation, computer arithmetic, exact real ari} }
Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)
Mark Braverman. Computability and Complexity of Julia Sets (Invited Talk). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, p. 3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{braverman:OASIcs.CCA.2009.2250, author = {Braverman, Mark}, title = {{Computability and Complexity of Julia Sets}}, booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)}, pages = {3--3}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-12-5}, ISSN = {2190-6807}, year = {2009}, volume = {11}, editor = {Bauer, Andrej and Hertling, Peter and Ko, Ker-I}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2250}, URN = {urn:nbn:de:0030-drops-22508}, doi = {10.4230/OASIcs.CCA.2009.2250}, annote = {Keywords: Computability, computable analysis, dynamical systems, complex dynamics, Julia sets Computability, computable analysis, dynamical systems, complex dynamics, Julia sets} }
Feedback for Dagstuhl Publishing