LIPIcs, Volume 107
ICALP 2018, July 9-13, 2018, Prague, Czech Republic
Editors: Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Enver Aman, Karthik C. S., and Sharath Punna. On Connections Between k-Coloring and Euclidean k-Means. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aman_et_al:LIPIcs.ESA.2024.9, author = {Aman, Enver and Karthik C. S. and Punna, Sharath}, title = {{On Connections Between k-Coloring and Euclidean k-Means}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {9:1--9: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.9}, URN = {urn:nbn:de:0030-drops-210808}, doi = {10.4230/LIPIcs.ESA.2024.9}, annote = {Keywords: k-means, k-minsum, Euclidean space, fine-grained complexity} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Shinwoo An, Eunjin Oh, and Jie Xue. Sparse Outerstring Graphs Have Logarithmic Treewidth. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{an_et_al:LIPIcs.ESA.2024.10, author = {An, Shinwoo and Oh, Eunjin and Xue, Jie}, title = {{Sparse Outerstring Graphs Have Logarithmic Treewidth}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {10:1--10: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.10}, URN = {urn:nbn:de:0030-drops-210816}, doi = {10.4230/LIPIcs.ESA.2024.10}, annote = {Keywords: Outerstring graphs, geometric intersection graphs, treewidth} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, and Saket Saurabh. Cuts in Graphs with Matroid Constraints. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{banik_et_al:LIPIcs.ESA.2024.17, author = {Banik, Aritra and Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Jana, Satyabrata and Saurabh, Saket}, title = {{Cuts in Graphs with Matroid Constraints}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {17:1--17:15}, 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.17}, URN = {urn:nbn:de:0030-drops-210887}, doi = {10.4230/LIPIcs.ESA.2024.17}, annote = {Keywords: s-t-cut, multiway Cut, matroid, odd cycle transversal, feedback vertex set, fixed-parameter tractability} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Cornelius Brand, Martin Koutecký, Alexandra Lassota, and Sebastian Ordyniak. Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{brand_et_al:LIPIcs.ESA.2024.32, author = {Brand, Cornelius and Kouteck\'{y}, Martin and Lassota, Alexandra and Ordyniak, Sebastian}, title = {{Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {32:1--32: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.32}, URN = {urn:nbn:de:0030-drops-211033}, doi = {10.4230/LIPIcs.ESA.2024.32}, annote = {Keywords: Mixed-Integer Programming, Separable Convex Optimization, Parameterized Algorithms, Parameterized Complexity} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Kevin Buchin, Maike Buchin, Joachim Gudmundsson, and Sampson Wong. Bicriteria Approximation for Minimum Dilation Graph Augmentation. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{buchin_et_al:LIPIcs.ESA.2024.36, author = {Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Wong, Sampson}, title = {{Bicriteria Approximation for Minimum Dilation Graph Augmentation}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {36:1--36:15}, 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.36}, URN = {urn:nbn:de:0030-drops-211079}, doi = {10.4230/LIPIcs.ESA.2024.36}, annote = {Keywords: Greedy spanner, Graph augmentation} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski. List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{canesmer_et_al:LIPIcs.ESA.2024.39, author = {Can Esmer, Bar{\i}\c{s} and Focke, Jacob and Marx, D\'{a}niel and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {39:1--39:20}, 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.39}, URN = {urn:nbn:de:0030-drops-211103}, doi = {10.4230/LIPIcs.ESA.2024.39}, annote = {Keywords: Graph Homomorphism, List Homomorphism, Vertex Deletion, Edge Deletion, Multiway Cut, Parameterized Complexity, Tight Bounds, Treewidth, SETH} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Chandra Chekuri, Rhea Jain, Shubhang Kulkarni, Da Wei Zheng, and Weihao Zhu. From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chekuri_et_al:LIPIcs.ESA.2024.42, author = {Chekuri, Chandra and Jain, Rhea and Kulkarni, Shubhang and Zheng, Da Wei and Zhu, Weihao}, title = {{From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {42:1--42:19}, 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.42}, URN = {urn:nbn:de:0030-drops-211134}, doi = {10.4230/LIPIcs.ESA.2024.42}, annote = {Keywords: Directed Planar Graphs, Submodular Functions, Steiner Tree, Network Design} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Jana Cslovjecsek, Michał Pilipczuk, and Karol Węgrzycki. Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cslovjecsek_et_al:LIPIcs.ESA.2024.43, author = {Cslovjecsek, Jana and Pilipczuk, Micha{\l} and W\k{e}grzycki, Karol}, title = {{Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {43:1--43: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.43}, URN = {urn:nbn:de:0030-drops-211146}, doi = {10.4230/LIPIcs.ESA.2024.43}, annote = {Keywords: parameterized approximation, Maximum Weight Independent Set, rectangles, segments} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Sally Dong and Guanghao Ye. Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dong_et_al:LIPIcs.ESA.2024.49, author = {Dong, Sally and Ye, Guanghao}, title = {{Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {49:1--49:14}, 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.49}, URN = {urn:nbn:de:0030-drops-211207}, doi = {10.4230/LIPIcs.ESA.2024.49}, annote = {Keywords: Min-cost flow, tree decomposition, interior point method, bounded treewidth graphs} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Lech Duraj, Filip Konieczny, and Krzysztof Potępa. Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{duraj_et_al:LIPIcs.ESA.2024.51, author = {Duraj, Lech and Konieczny, Filip and Pot\k{e}pa, Krzysztof}, title = {{Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {51:1--51: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.51}, URN = {urn:nbn:de:0030-drops-211229}, doi = {10.4230/LIPIcs.ESA.2024.51}, annote = {Keywords: Graph Diameter, Geometric Intersection Graphs, Vapnik-Chervonenkis Dimension} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, and Karol Węgrzycki. Hitting Meets Packing: How Hard Can It Be?. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 55:1-55:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{focke_et_al:LIPIcs.ESA.2024.55, author = {Focke, Jacob and Frei, Fabian and Li, Shaohua and Marx, D\'{a}niel and Schepper, Philipp and Sharma, Roohani and W\k{e}grzycki, Karol}, title = {{Hitting Meets Packing: How Hard Can It Be?}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {55:1--55:21}, 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.55}, URN = {urn:nbn:de:0030-drops-211261}, doi = {10.4230/LIPIcs.ESA.2024.55}, annote = {Keywords: Hitting, Packing, Covering, Parameterized Algorithms, Lower Bounds, Treewidth} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Dvir Fried, Tsvi Kopelowitz, and Ely Porat. Removing the log Factor from (min,+)-Products on Bounded Range Integer Matrices. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 57:1-57:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fried_et_al:LIPIcs.ESA.2024.57, author = {Fried, Dvir and Kopelowitz, Tsvi and Porat, Ely}, title = {{Removing the log Factor from (min,+)-Products on Bounded Range Integer Matrices}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {57:1--57:6}, 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.57}, URN = {urn:nbn:de:0030-drops-211283}, doi = {10.4230/LIPIcs.ESA.2024.57}, annote = {Keywords: FMM, (min , +)-product, FFT} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Mohit Garg, Debajyoti Kar, and Arindam Khan. Random-Order Online Independent Set of Intervals and Hyperrectangles. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{garg_et_al:LIPIcs.ESA.2024.58, author = {Garg, Mohit and Kar, Debajyoti and Khan, Arindam}, title = {{Random-Order Online Independent Set of Intervals and Hyperrectangles}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {58:1--58: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.58}, URN = {urn:nbn:de:0030-drops-211298}, doi = {10.4230/LIPIcs.ESA.2024.58}, annote = {Keywords: Online Algorithms, Random-Order Model, Maximum Independent Set of Rectangles, Hyperrectangles, Fat Objects, Interval Scheduling} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Bart M.P. Jansen and Céline M.F. Swennenhuis. Steiner Tree Parameterized by Multiway Cut and Even Less. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 76:1-76:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jansen_et_al:LIPIcs.ESA.2024.76, author = {Jansen, Bart M.P. and Swennenhuis, C\'{e}line M.F.}, title = {{Steiner Tree Parameterized by Multiway Cut and Even Less}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {76:1--76:16}, 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.76}, URN = {urn:nbn:de:0030-drops-211471}, doi = {10.4230/LIPIcs.ESA.2024.76}, annote = {Keywords: fixed-parameter tractability, Steiner Tree, structural parameterization, H-treewidth} }
Feedback for Dagstuhl Publishing