Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Manuel Cáceres, Massimo Cairo, Andreas Grigorjew, Shahbaz Khan, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu, and Lucia Williams. Width Helps and Hinders Splitting Flows. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{caceres_et_al:LIPIcs.ESA.2022.31, author = {C\'{a}ceres, Manuel and Cairo, Massimo and Grigorjew, Andreas and Khan, Shahbaz and Mumey, Brendan and Rizzi, Romeo and Tomescu, Alexandru I. and Williams, Lucia}, title = {{Width Helps and Hinders Splitting Flows}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {31:1--31: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.31}, URN = {urn:nbn:de:0030-drops-169695}, doi = {10.4230/LIPIcs.ESA.2022.31}, annote = {Keywords: Flow decomposition, approximation algorithms, graph width} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Andreas Björklund and Petteri Kaski. Counting Short Vector Pairs by Inner Product and Relations to the Permanent. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2021.29, author = {Bj\"{o}rklund, Andreas and Kaski, Petteri}, title = {{Counting Short Vector Pairs by Inner Product and Relations to the Permanent}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {29:1--29:21}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.29}, URN = {urn:nbn:de:0030-drops-140988}, doi = {10.4230/LIPIcs.ICALP.2021.29}, annote = {Keywords: additive reconstruction, Chinese Remainder Theorem, counting, inner product, modular tomography, orthogonal vectors, permanent} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Tuukka Korhonen. Lower Bounds on Dynamic Programming for Maximum Weight Independent Set. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 87:1-87:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{korhonen:LIPIcs.ICALP.2021.87, author = {Korhonen, Tuukka}, title = {{Lower Bounds on Dynamic Programming for Maximum Weight Independent Set}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {87:1--87:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.87}, URN = {urn:nbn:de:0030-drops-141562}, doi = {10.4230/LIPIcs.ICALP.2021.87}, annote = {Keywords: Maximum weight independent set, Treewidth, Tropical circuits, Dynamic programming, Treedepth, Monotone circuit complexity} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Dömötör Pálvölgyi. Radon Numbers Grow Linearly. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 60:1-60:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{palvolgyi:LIPIcs.SoCG.2020.60, author = {P\'{a}lv\"{o}lgyi, D\"{o}m\"{o}t\"{o}r}, title = {{Radon Numbers Grow Linearly}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {60:1--60:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.60}, URN = {urn:nbn:de:0030-drops-122183}, doi = {10.4230/LIPIcs.SoCG.2020.60}, annote = {Keywords: discrete geometry, convexity space, Radon number} }
Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)
Roland Wittler. Alignment- and Reference-Free Phylogenomics with Colored de Bruijn Graphs. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{wittler:LIPIcs.WABI.2019.2, author = {Wittler, Roland}, title = {{Alignment- and Reference-Free Phylogenomics with Colored de Bruijn Graphs}}, booktitle = {19th International Workshop on Algorithms in Bioinformatics (WABI 2019)}, pages = {2:1--2:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-123-8}, ISSN = {1868-8969}, year = {2019}, volume = {143}, editor = {Huber, Katharina T. and Gusfield, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.2}, URN = {urn:nbn:de:0030-drops-110325}, doi = {10.4230/LIPIcs.WABI.2019.2}, annote = {Keywords: Phylogenomics, phylogenetics, phylogenetic splits, colored de Bruijn graphs} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Andreas Bärtschi, Daniel Graf, and Matús Mihalák. Collective Fast Delivery by Energy-Efficient Agents. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 56:1-56:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bartschi_et_al:LIPIcs.MFCS.2018.56, author = {B\"{a}rtschi, Andreas and Graf, Daniel and Mihal\'{a}k, Mat\'{u}s}, title = {{Collective Fast Delivery by Energy-Efficient Agents}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {56:1--56:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.56}, URN = {urn:nbn:de:0030-drops-96381}, doi = {10.4230/LIPIcs.MFCS.2018.56}, annote = {Keywords: delivery, mobile agents, time/energy optimization, complexity, algorithms} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chitnis_et_al:LIPIcs.ESA.2018.20, author = {Chitnis, Rajesh and Feldmann, Andreas Emil and Manurangsi, Pasin}, title = {{Parameterized Approximation Algorithms for Bidirected Steiner Network Problems}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {20:1--20: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.20}, URN = {urn:nbn:de:0030-drops-94833}, doi = {10.4230/LIPIcs.ESA.2018.20}, annote = {Keywords: Directed Steiner Network, Strongly Connected Steiner Subgraph, Parameterized Approximations, Bidirected Graphs, Planar Graphs} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Andreas Schmid and Jens M. Schmidt. Computing Tutte Paths. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 98:1-98:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{schmid_et_al:LIPIcs.ICALP.2018.98, author = {Schmid, Andreas and Schmidt, Jens M.}, title = {{Computing Tutte Paths}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {98:1--98: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.98}, URN = {urn:nbn:de:0030-drops-91029}, doi = {10.4230/LIPIcs.ICALP.2018.98}, annote = {Keywords: Tutte Path, Tutte Cycle, 2-Connected Planar Graph, Hamiltonian Cycle} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Andreas Haas. Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{haas:LIPIcs.SoCG.2018.44, author = {Haas, Andreas}, title = {{Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {44:1--44:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.44}, URN = {urn:nbn:de:0030-drops-87576}, doi = {10.4230/LIPIcs.SoCG.2018.44}, annote = {Keywords: computational geometry, minimum-weight triangulation} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Fábio Botler, Andrés Cristi, Ruben Hoeksma, Kevin Schewior, and Andreas Tönnis. SUPERSET: A (Super)Natural Variant of the Card Game SET. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{botler_et_al:LIPIcs.FUN.2018.12, author = {Botler, F\'{a}bio and Cristi, Andr\'{e}s and Hoeksma, Ruben and Schewior, Kevin and T\"{o}nnis, Andreas}, title = {{SUPERSET: A (Super)Natural Variant of the Card Game SET}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.12}, URN = {urn:nbn:de:0030-drops-88035}, doi = {10.4230/LIPIcs.FUN.2018.12}, annote = {Keywords: SET, SUPERSET, card game, cap set, affine geometry, computational complexity} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Andreas Emil Feldmann and Dániel Marx. The Parameterized Hardness of the k-Center Problem in Transportation Networks. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{feldmann_et_al:LIPIcs.SWAT.2018.19, author = {Feldmann, Andreas Emil and Marx, D\'{a}niel}, title = {{The Parameterized Hardness of the k-Center Problem in Transportation Networks}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {19:1--19:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.19}, URN = {urn:nbn:de:0030-drops-88450}, doi = {10.4230/LIPIcs.SWAT.2018.19}, annote = {Keywords: k-center, parameterized complexity, planar graphs, doubling dimension, highway dimension, treewidth} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Peter Chini, Jonathan Kolberg, Andreas Krebs, Roland Meyer, and Prakash Saivasan. On the Complexity of Bounded Context Switching. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chini_et_al:LIPIcs.ESA.2017.27, author = {Chini, Peter and Kolberg, Jonathan and Krebs, Andreas and Meyer, Roland and Saivasan, Prakash}, title = {{On the Complexity of Bounded Context Switching}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.27}, URN = {urn:nbn:de:0030-drops-78730}, doi = {10.4230/LIPIcs.ESA.2017.27}, annote = {Keywords: Shared memory concurrency, safety verification, fixed-parameter tractability, exponential time hypothesis, bounded context switching} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Thomas Kesselheim and Andreas Tönnis. Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{kesselheim_et_al:LIPIcs.APPROX-RANDOM.2017.16, author = {Kesselheim, Thomas and T\"{o}nnis, Andreas}, title = {{Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {16:1--16:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, 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.2017.16}, URN = {urn:nbn:de:0030-drops-75657}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.16}, annote = {Keywords: Secretary Problem, Online Algorithms, Submodular Maximization} }
Published in: LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016)
Andreas Haas, Thomas A. Henzinger, Andreas Holzer, Christoph M. Kirsch, Michael Lippautz, Hannes Payer, Ali Sezgin, Ana Sokolova, and Helmut Veith. Local Linearizability for Concurrent Container-Type Data Structures. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{haas_et_al:LIPIcs.CONCUR.2016.6, author = {Haas, Andreas and Henzinger, Thomas A. and Holzer, Andreas and Kirsch, Christoph M. and Lippautz, Michael and Payer, Hannes and Sezgin, Ali and Sokolova, Ana and Veith, Helmut}, title = {{Local Linearizability for Concurrent Container-Type Data Structures}}, booktitle = {27th International Conference on Concurrency Theory (CONCUR 2016)}, pages = {6:1--6:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-017-0}, ISSN = {1868-8969}, year = {2016}, volume = {59}, editor = {Desharnais, Jos\'{e}e and Jagadeesan, Radha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.6}, URN = {urn:nbn:de:0030-drops-61809}, doi = {10.4230/LIPIcs.CONCUR.2016.6}, annote = {Keywords: (concurrent) data structures, relaxed semantics, linearizability} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Thomas Kesselheim and Andreas Tönnis. Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{kesselheim_et_al:LIPIcs.ESA.2016.54, author = {Kesselheim, Thomas and T\"{o}nnis, Andreas}, title = {{Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {54:1--54:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.54}, URN = {urn:nbn:de:0030-drops-63966}, doi = {10.4230/LIPIcs.ESA.2016.54}, annote = {Keywords: Secretary Problem, Online Algorithms, Scheduling Problems} }
Feedback for Dagstuhl Publishing