default search action
33rd ESA 2025: Warsaw, Poland
- Anne Benoit
, Haim Kaplan
33rd Annual European Symposium on Algorithms, ESA 2025, September 15-17, 2025, Warsaw, Poland. LIPIcs 351, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2025, ISBN 978-3-95977-395-9 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xxvi
- Bernhard Haeupler:
Graph Decompositions and Length-Constrained Expanders (Invited Talk). 1:1-1:2 - Monika Henzinger, Roodabeh Safavi:
Securing Dynamic Data: A Primer on Differentially Private Data Structures (Invited Talk). 2:1-2:14 - Baris Can Esmer, Dániel Marx:
Generalized Graph Packing Problems Parameterized by Treewidth. 3:1-3:15 - Wang Fang, Qisheng Wang:
Optimal Quantum Algorithm for Estimating Fidelity to a Pure State. 4:1-4:12 - Gerth Stølting Brodal, Michael T. Goodrich, John Iacono, Jared Lo, Ulrich Meyer, Victor Pagan, Nodari Sitchinava, Rolf Svenning:
External-Memory Priority Queues with Optimal Insertions. 5:1-5:14 - Jens Schlöter:
On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms. 6:1-6:15 - Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos:
Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion. 7:1-7:18 - Yuto Nakashima, Jakub Radoszewski, Tomasz Walen:
Fast Computation of k-Runs, Parameterized Squares, and Other Generalised Squares. 8:1-8:18 - Stefan Hermann:
MorphisHash: Improving Space Efficiency of ShockHash for Minimal Perfect Hashing. 9:1-9:16 - Aikaterini Niklanovits, Kirill Simonov, Shaily Verma, Ziena Zeif:
Connected Partitions via Connected Dominating Sets. 10:1-10:14 - Tatsuya Gima, Soh Kumabe, Yuichi Yoshida:
Courcelle's Theorem for Lipschitz Continuity. 11:1-11:14 - Jacobus Conradi, Anne Driemel:
Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better. 12:1-12:18 - Narek Bojikian, Vera Chekan, Stefan Kratsch:
Tight Bounds for Some Classical Problems Parameterized by Cutwidth. 13:1-13:17 - Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir:
Testing Sumsets Is Hard. 14:1-14:16 - Thomas Depian, Simon D. Fink, Robert Ganian, Vaishali Surianarayanan:
Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms. 15:1-15:18 - Benjamin Bergougnoux, Thekla Hamm, Lars Jaffke, Paloma T. Lima:
On Algorithmic Applications of ℱ-Branchwidth. 16:1-16:17 - Ahammed Ullah, S. M. Ferdous, Alex Pothen:
Weighted Matching in a Poly-Streaming Model. 17:1-17:18 - Md. Hasin Abrar, Paul Medvedev, Giorgio Vinciguerra:
Efficiency of Learned Indexes on Genome Spectra. 18:1-18:18 - Nicolas El Maalouly, Sebastian Haslebacher
On Finding 𝓁-Th Smallest Perfect Matchings. 19:1-19:15 - Pawel Garncarek, Dariusz R. Kowalski, Shay Kutten, Miguel A. Mosteiro:
Beeping Deterministic CONGEST Algorithms in Graphs. 20:1-20:17 - Éric Colin de Verdière, Petr Hlinený:
A Unified FPT Framework for Crossing Number Problems. 21:1-21:18 - Christian Konrad, Chhaya Trehan:
Constructing Long Paths in Graph Streams. 22:1-22:19 - Gianmarco Picarella, Marc J. van Kreveld, Frank Staals, Sjoerd de Vries:
Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter. 23:1-23:16 - Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg, Lasse Wulf:
Fréchet Distance in Unweighted Planar Graphs. 24:1-24:16 - Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, Sampson Wong:
Instance-Optimal Imprecise Convex Hull. 25:1-25:15 - Loukas Georgiadis
Faster Dynamic 2-Edge Connectivity in Directed Graphs. 26:1-26:16 - Ekin Ergen:
Online Makespan Scheduling Under Scenarios. 27:1-27:16 - Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, Tobias Wallner:
Sliding Squares in Parallel. 28:1-28:17 - Nicolas Bousquet, Quentin Deschamps, Arnaud Mary, Amer E. Mouawad, Théo Pierron:
The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration. 29:1-29:15 - Michael Krivelevich, Maksim Zhukovskii:
Reconstructing Random Graphs from Distance Queries. 30:1-30:17 - Bruce W. Brewer, Haitao Wang:
An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs. 31:1-31:8 - Lars Gottesbüren, Nikolai Maas, Dominik Rosch, Peter Sanders, Daniel Seemaier:
Linear-Time Multilevel Graph Partitioning via Edge Sparsification. 32:1-32:20 - Pawel Gawrychowski, Adam Górkiewicz:
Better Indexing for Rectangular Pattern Matching. 33:1-33:7 - Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, Laura Vargas Koch:
On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem. 34:1-34:15 - Thijs van der Horst, Marc J. van Kreveld, Tim Ophelders, Bettina Speckmann:
The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon. 35:1-35:16 - Monika Henzinger, Evangelos Kosinas, Robin Münk, Harald Räcke:
Efficient Contractions of Dynamic Graphs - With Applications. 36:1-36:14 - Henrique Ennes, Clément Maria:
Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology. 37:1-37:16 - Nikhil Kumar, J. J. Nan, Chaitanya Swamy:
Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique. 38:1-38:18 - Michal Wlodarczyk:
Going Beyond Surfaces in Diameter Approximation. 39:1-39:19 - Esther Galby, Paloma T. Lima, Andrea Munaro, Amir Nikabadi
Maximum List r-Colorable Induced Subgraphs in kP₃-Free Graphs. 40:1-40:13 - Nairen Cao, Steven Roche, Hsin-Hao Su:
Min-Max Correlation Clustering via Neighborhood Similarity. 41:1-41:18 - Geri Gokaj, Marvin Künnemann, Sabine Storandt, Carina Truschel:
(Multivariate) k-SUM as Barrier to Succinct Computation. 42:1-42:19 - Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov:
Edge Clique Partition and Cover Beyond Independence. 43:1-43:16 - Koustav Bhanja, Asaf Petruschka:
Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity. 44:1-44:13 - Itai Boneh, Egor Gorbachev, Tomasz Kociumaka:
Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds. 45:1-45:16 - Soh Kumabe:
Max-Distance Sparsification for Diversification and Clustering. 46:1-46:14 - Manuel Haag, Florian Kurpicz, Peter Sanders, Matthias Schimek:
Fast and Lightweight Distributed Suffix Array Construction. 47:1-47:18 - Klaus Jansen, Lis Pirotton, Malte Tutas:
The Support of Bin Packing Is Exponential. 48:1-48:16 - Vincent Jugé:
Efficient Top-Down Updates in AVL Trees. 49:1-49:15 - Minati De, Satyam Singh, Csaba D. Tóth:
Online Hitting Sets for Disks of Bounded Radii. 50:1-50:16 - Minbo Gao, Zhengfeng Ji, Qisheng Wang:
Quantum Approximate k-Minimum Finding. 51:1-51:15 - Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, Jan Olkowski:
Beating Competitive Ratio 4 for Graphic Matroid Secretary. 52:1-52:16 - Ben Bals, Sebastiaan van Krieken, Solon P. Pissis, Leen Stougie, Hilde Verbeek:
When Is String Reconstruction Using de Bruijn Graphs Hard? 53:1-53:16 - Bingbing Hu, Adam Polak:
Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems. 54:1-54:16 - Francisco Sena, Romeo Rizzi, Alexandru I. Tomescu:
Safe Sequences via Dominators in DAGs for Path-Covering Problems. 55:1-55:17 - Dominik Scheder, Johannes Tantow:
PLS-Completeness of String Permutations. 56:1-56:14 - Sam Hiken, Nicole Wein:
Improved Hardness-Of-Approximation for Token-Swapping. 57:1-57:16 - Magnús M. Halldórsson, Nicolaos Matsakis, Pavel Veselý:
Streaming Diameter of High-Dimensional Points. 58:1-58:10 - Konstantinos Karathanasis, Spyros C. Kontogiannis, Christos D. Zaroliagis:
Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets. 59:1-59:17 - Jannik Olbrich:
Fast and Memory-Efficient BWT Construction of Repetitive Texts Using Lyndon Grammars. 60:1-60:19 - Vincent Despré, Camille Lanuel, Marc Pouget, Monique Teillaud:
ε-Net Algorithm Implementation on Hyperbolic Surfaces. 61:1-61:18 - Sina Bagheri Nezhad, Sayan Bandyapadhyay, Tianzhi Chen:
Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering. 62:1-62:16 - Jan Eube, Kelin Luo, Dorian Reineccius, Heiko Röglin, Melanie Schmidt:
Connected k-Median with Disjoint and Non-Disjoint Clusters. 63:1-63:14 - Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg, Tord Stordalen:
A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees. 64:1-64:18 - Ernestine Großmann, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Ivor van der Hoog, Juliette Vlieghe:
From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation. 65:1-65:18 - Zeev Nutov, Reut Cohen:
Bicriteria Approximation for k-Edge-Connectivity. 66:1-66:17 - Jean Cardinal, Yelena Yuditsky:
Compact Representation of Semilinear and Terrain-Like Graphs. 67:1-67:19 - Surender Baswana, Koustav Bhanja, Anupam Roy
Faster Algorithm for Second (s, t)-Mincut and Breaking Quadratic Barrier for Dual Edge Sensitivity for (s, t)-Mincut. 68:1-68:19 - David Eppstein, Michael T. Goodrich, Songyu Liu:
Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing. 69:1-69:17 - Jeff Giliberti, David G. Harris:
Improved Parallel Derandomization via Finite Automata with Applications. 70:1-70:17 - Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann:
Simpler Universally Optimal Dijkstra. 71:1-71:9 - Noam Horowicz, Tsvi Kopelowitz:
Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions. 72:1-72:17 - François Le Gall:
Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians. 73:1-73:19 - Pawel Gawrychowski, Egor Gorbachev, Tomasz Kociumaka:
Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications. 74:1-74:17 - Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist
An Improved Bound for Plane Covering Paths. 75:1-75:10 - Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Lukasz Jez, Jirí Sgall, Agnieszka Tatarczuk:
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs. 76:1-76:15 - Reut Levi, Jonathan Meiri:
Tolerant Testers for Subgraph-Freeness. 77:1-77:15 - Artur Czumaj, Christian Sohler, Stefan Walzer:
Testing Depth First Search Numbering. 78:1-78:16 - Henrik Reinstädtler, S. M. Ferdous, Alex Pothen, Bora Uçar, Christian Schulz:
Semi-Streaming Algorithms for Hypergraph Matching. 79:1-79:19 - Christian Bertram:
Online Metric TSP. 80:1-80:9 - Mark de Berg, Sergio Cabello:
An O(nlog n) Algorithm for Single-Source Shortest Paths in Disk Graphs. 81:1-81:15 - Gerth Stølting Brodal, Casper Moldrup Rysgaard, Rolf Svenning:
Buffered Partially-Persistent External-Memory Search Trees. 82:1-82:18 - Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Laure Morelle:
Fault-Tolerant Matroid Bases. 83:1-83:14 - Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, Sampson Wong:
Property Testing of Curve Similarity. 84:1-84:16 - Stefan Walzer, Marvin Williams:
A Simple yet Exact Analysis of the MultiQueue. 85:1-85:14 - Ce Jin, Ryan Williams, Stan Zhang:
New Algorithms for Pigeonhole Equal Subset Sum. 86:1-86:12 - Florian Hörsch, Dániel Marx:
Multicut Problems in Almost-Planar Graphs: the Dependency of Complexity on the Demand Pattern. 87:1-87:13 - Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Magnus Wahlström:
Parameterized Approximability for Modular Linear Equations. 88:1-88:15 - Nick Fischer, Melvin Kallmayer, Leo Wennmann:
A Simple Algorithm for Trimmed Multipoint Evaluation. 89:1-89:11 - Jack Spalding-Jamieson, Anurag Murty Naredla:
Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds. 90:1-90:18 - Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, Leqi Zhu:
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism. 91:1-91:20 - Yann Disser, David Weckbecker:
Incremental Maximization for a Broad Class of Objectives. 92:1-92:13 - Thomas Erlebach, Othon Michail, Nils Morawietz:
Recognizing and Realizing Temporal Reachability Graphs. 93:1-93:18 - Tomasz Kociumaka, Ali Shahali:
Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime. 94:1-94:16 - David Kühnemann, Adam Polak, Alon Rosen:
The Planted Orthogonal Vectors Problem. 95:1-95:17 - Radu Curticapean, Simon Döring, Daniel Neuen:
Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial. 96:1-96:16 - Saman Ahmadi, Andrea Raith, Mahdi Jalili:
A Fast and Simple Algorithm for the Resource Constrained Shortest Path Problem. 97:1-97:15 - Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic:
Fine-Grained Classification of Detecting Dominating Patterns. 98:1-98:15 - Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann, Peter Sanders, Stefan Walzer:
Engineering Minimal k-Perfect Hash Functions. 99:1-99:18 - Yotam Kenneth-Mordoch, Robert Krauthgamer:
Cut-Query Algorithms with Few Rounds. 100:1-100:14 - Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, James Sud:
Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings. 101:1-101:14 - Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann:
A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull. 102:1-102:13 - Ioannis Caragiannis, Nick Gravin, Zhile Jiang:
On the Satisfiability of Random 3-SAT Formulas with k-Wise Independent Clauses. 103:1-103:17 - Benjamin Aram Berendsohn:
Optimal Antimatroid Sorting. 104:1-104:14 - Joshua Könen, Heiko Röglin, Tarek Stuck:
Parameterized Algorithms for Computing Pareto Sets. 105:1-105:15 - Yupan Liu, Qisheng Wang:
On Estimating the Quantum 𝓁α Distance. 106:1-106:19 - Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang:
Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts. 107:1-107:17 - Matej Lieskovský:
Deterministic Approximation Algorithm for Graph Burning. 108:1-108:7 - Hans-Peter Lehmann, Peter Sanders, Stefan Walzer, Jonatan Ziegler:
Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing. 109:1-109:18 - László Kozma, Junqi Tan:
Faster Exponential Algorithms for Cut Problems via Geometric Data Structures. 110:1-110:12 - Nick Fischer, Elazar Goldenberg, Mursalin Habib, Karthik C. S.:
Hardness of Median and Center in the Ulam Metric. 111:1-111:17 - Mariia Anapolska, Dario van den Boom, Christina Büsing, Timo Gersing:
A Faster Parametric Search for the Integral Quickest Transshipment Problem. 112:1-112:15 - Rasmus Kyng, Simon Meierhans, Gernot Zöcklein:
Bootstrapping Dynamic APSP via Sparsification. 113:1-113:15 - Haitao Wang:
A Deterministic Partition Tree and Applications. 114:1-114:17 - Christian Coester, Jack Umenberger:
Smoothed Analysis of Online Metric Problems. 115:1-115:14 - Martin Fürer, Carlos Hoppen
Fast Gaussian Elimination for Low Treewidth Matrices. 116:1-116:15
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-14 22:25 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: