Portal - ESA 2022

ESA 2022	September 5-9, 2022, Berlin/Potsdam, Germany
30th Annual European Symposium on Algorithms (ESA 2022) Shiri Chechik and Gonzalo Navarro and Eva Rotenberg and Grzegorz Herman (Eds.)
ISBN 978-3-95977-247-1, LIPICS Vol. 244	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 36 MB)
Search Publication Server

Authors

Bumpus, Benjamin Merlin

Cairo, Massimo

Chakrabarti, Amit

Chakrabarty, Deeparnab

Chakraborty, Sourav

Chaplick, Steven

Charalampopoulos, Panagiotis

D'Angelo, Gianlorenzo

de Lima, Murilo Santos

Flores-Velazco, Alejandro

Hershkowitz, D. Ellis

Italiano, Giuseppe F.

Kisfaludi-Bak, Sándor

Rasmussen, Anna Rodriguez

Resende, Mauricio G.C.

Saranurak, Thatchaphol

Schwiegelshohn, Chris

Sheikh-Omar, Omar Ali

Theocharous, Leonidas

Tiskin, Alexander

Tomescu, Alexandru I.

Vassilevska Williams, Virginia

Vermeulen, Jordi L.

Villedieu, Anaïs

Vinodchandran¹, N. V.

Łukasiewicz, Aleksander

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Chechik, Shiri ; Navarro, Gonzalo ; Rotenberg, Eva ; Herman, Grzegorz

Abstract | Document (516 KB) | BibTeX

Enumerating Minimal Connected Dominating Sets

Authors: Abu-Khzam, Faisal N. ; Fernau, Henning ; Gras, Benjamin ; Liedloff, Mathieu ; Mann, Kevin

Abstract | Document (858 KB) | BibTeX

Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries

Authors: Addanki, Raghavendra ; McGregor, Andrew ; Musco, Cameron

Abstract | Document (879 KB) | BibTeX

Hardness of Token Swapping on Trees

Authors: Aichholzer, Oswin ; Demaine, Erik D. ; Korman, Matias ; Lubiw, Anna ; Lynch, Jayson ; Masárová, Zuzana ; Rudoy, Mikhail ; Vassilevska Williams, Virginia ; Wein, Nicole

Abstract | Document (1,373 KB) | BibTeX

Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities

Authors: Albers, Susanne ; Schubert, Sebastian

Abstract | Document (774 KB) | BibTeX

TSP in a Simple Polygon

Authors: Alkema, Henk ; de Berg, Mark ; Monemizadeh, Morteza ; Theocharous, Leonidas

Abstract | Document (946 KB) | BibTeX

Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming

Authors: Allcock, Jonathan ; Hamoudi, Yassine ; Joux, Antoine ; Klingelhöfer, Felix ; Santha, Miklos

Abstract | Document (1,360 KB) | BibTeX

Techniques for Generalized Colorful k-Center Problems

Authors: Anegg, Georg ; Vargas Koch, Laura ; Zenklusen, Rico

Abstract | Document (1,133 KB) | BibTeX

Simple Streaming Algorithms for Edge Coloring

Authors: Ansari, Mohammad ; Saneian, Mohammad ; Zarrabi-Zadeh, Hamid

Abstract | Document (483 KB) | BibTeX

Computing Smallest Convex Intersecting Polygons

Authors: Antoniadis, Antonios ; de Berg, Mark ; Kisfaludi-Bak, Sándor ; Skarlatos, Antonis

Abstract | Document (915 KB) | BibTeX

The Price of Hierarchical Clustering

Authors: Arutyunova, Anna ; Röglin, Heiko

Abstract | Document (807 KB) | BibTeX

Bounding and Computing Obstacle Numbers of Graphs

Authors: Balko, Martin ; Chaplick, Steven ; Ganian, Robert ; Gupta, Siddharth ; Hoffmann, Michael ; Valtr, Pavel ; Wolff, Alexander

Abstract | Document (1,029 KB) | BibTeX

Computing NP-Hard Repetitiveness Measures via MAX-SAT

Authors: Bannai, Hideo ; Goto, Keisuke ; Ishihata, Masakazu ; Kanda, Shunsuke ; Köppl, Dominik ; Nishimoto, Takaaki

Abstract | Document (1,155 KB) | BibTeX

Online Metric Allocation and Time-Varying Regularization

Authors: Bansal, Nikhil ; Coester, Christian

Abstract | Document (688 KB) | BibTeX

An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions

Authors: Barth, Florian ; Funke, Stefan ; Proissl, Claudius

Abstract | Document (894 KB) | BibTeX

Galactic Token Sliding

Authors: Bartier, Valentin ; Bousquet, Nicolas ; Mouawad, Amer E.

Abstract | Document (775 KB) | BibTeX

When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting

Authors: Bhattacharya, Arghya ; Chowdhury, Abiyaz ; Xu, Helen ; Das, Rathish ; Chowdhury, Rezaul A. ; Johnson, Rob ; Nithyanand, Rishab ; Bender, Michael A.

Abstract | Document (628 KB) | BibTeX

Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary

Authors: Bhattacharya, Sayan ; Saranurak, Thatchaphol ; Sukprasert, Pattara

Abstract | Document (879 KB) | BibTeX

Online Spanners in Metric Spaces

Authors: Bhore, Sujoy ; Filtser, Arnold ; Khodabandeh, Hadi ; Tóth, Csaba D.

Abstract | Document (962 KB) | BibTeX

Sparse Temporal Spanners with Low Stretch

Authors: Bilò, Davide ; D'Angelo, Gianlorenzo ; Gualà, Luciano ; Leucci, Stefano ; Rossi, Mirko

Abstract | Document (1,142 KB) | BibTeX

Resource Sharing Revisited: Local Weak Duality and Optimal Convergence

Authors: Blankenburg, Daniel

Abstract | Document (912 KB) | BibTeX

On the External Validity of Average-Case Analyses of Graph Algorithms

Authors: Bläsius, Thomas ; Fischbeck, Philipp

Abstract | Document (1,161 KB) | BibTeX

On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations

Authors: Blažej, Václav ; Choudhary, Pratibha ; Knop, Dušan ; Schierreich, Šimon ; Suchý, Ondřej ; Valla, Tomáš

Abstract | Document (798 KB) | BibTeX

Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case

Authors: Bodek, Kobi ; Feldman, Moran

Abstract | Document (846 KB) | BibTeX

List Colouring Trees in Logarithmic Space

Authors: Bodlaender, Hans L. ; Groenland, Carla ; Jacob, Hugo

Abstract | Document (857 KB) | BibTeX

Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget

Authors: Bosek, Bartłomiej ; Zych-Pawlewicz, Anna

Abstract | Document (865 KB) | BibTeX

Polynomial Kernel for Immersion Hitting in Tournaments

Authors: Bożyk, Łukasz ; Pilipczuk, Michał

Abstract | Document (837 KB) | BibTeX

A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension

Authors: Brachter, Jendrik ; Schweitzer, Pascal

Abstract | Document (659 KB) | BibTeX

Faster Approximate Covering of Subcurves Under the Fréchet Distance

Authors: Brüning, Frederik ; Conradi, Jacobus ; Driemel, Anne

Abstract | Document (970 KB) | BibTeX

Efficient Fréchet Distance Queries for Segments

Authors: Buchin, Maike ; van der Hoog, Ivor ; Ophelders, Tim ; Schlipf, Lena ; Silveira, Rodrigo I. ; Staals, Frank

Abstract | Document (828 KB) | BibTeX

Search-Space Reduction via Essential Vertices

Authors: Bumpus, Benjamin Merlin ; Jansen, Bart M. P. ; de Kroon, Jari J. H.

Abstract | Document (1,049 KB) | BibTeX

Width Helps and Hinders Splitting Flows

Authors: Cáceres, Manuel ; Cairo, Massimo ; Grigorjew, Andreas ; Khan, Shahbaz ; Mumey, Brendan ; Rizzi, Romeo ; Tomescu, Alexandru I. ; Williams, Lucia

Abstract | Document (1,242 KB) | BibTeX

Counting Simplices in Hypergraph Streams

Authors: Chakrabarti, Amit ; Haris, Themistoklis

Abstract | Document (852 KB) | BibTeX

Approximation Algorithms for Continuous Clustering and Facility Location Problems

Authors: Chakrabarty, Deeparnab ; Negahbani, Maryam ; Sarkar, Ankita

Abstract | Document (836 KB) | BibTeX

Distinct Elements in Streams: An Algorithm for the (Text) Book

Authors: Chakraborty, Sourav ; Vinodchandran¹, N. V. ; Meel, Kuldeep S.

Abstract | Document (711 KB) | BibTeX

Approximate Circular Pattern Matching

Authors: Charalampopoulos, Panagiotis ; Kociumaka, Tomasz ; Radoszewski, Jakub ; Pissis, Solon P. ; Rytter, Wojciech ; Waleń, Tomasz ; Zuba, Wiktor

Abstract | Document (1,063 KB) | BibTeX

Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space

Authors: Chen, Jiehua ; Roy, Sanjukta

Abstract | Document (798 KB) | BibTeX

Spanner Approximations in Practice

Authors: Chimani, Markus ; Stutzenstein, Finn

Abstract | Document (1,991 KB) | BibTeX

Determinants from Homomorphisms

Authors: Curticapean, Radu

Abstract | Document (614 KB) | BibTeX

Conditional Lower Bounds for Dynamic Geometric Measure Problems

Authors: Dallant, Justin ; Iacono, John

Abstract | Document (1,159 KB) | BibTeX

A Simpler QPTAS for Scheduling Jobs with Precedence Constraints

Authors: Das, Syamantak ; Wiese, Andreas

Abstract | Document (597 KB) | BibTeX

A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games

Authors: Deligkas, Argyrios ; Fasoulakis, Michail ; Markakis, Evangelos

Abstract | Document (718 KB) | BibTeX

Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem

Authors: Dey, Dipan ; Gupta, Manoj

Abstract | Document (825 KB) | BibTeX

Fast Computation of Zigzag Persistence

Authors: Dey, Tamal K. ; Hou, Tao

Abstract | Document (828 KB) | BibTeX

Turbocharging Heuristics for Weak Coloring Numbers

Authors: Dobler, Alexander ; Sorge, Manuel ; Villedieu, Anaïs

Abstract | Document (1,197 KB) | BibTeX

A Local Search Algorithm for Large Maximum Weight Independent Set Problems

Authors: Dong, Yuanyuan ; Goldberg, Andrew V. ; Noe, Alexander ; Parotsidis, Nikos ; Resende, Mauricio G.C. ; Spaen, Quico

Abstract | Document (4,101 KB) | BibTeX

SAT Backdoors: Depth Beats Size

Authors: Dreier, Jan ; Ordyniak, Sebastian ; Szeider, Stefan

Abstract | Document (973 KB) | BibTeX

Finding a Cluster in Incomplete Data

Authors: Eiben, Eduard ; Ganian, Robert ; Kanj, Iyad ; Ordyniak, Sebastian ; Szeider, Stefan

Abstract | Document (725 KB) | BibTeX

Lyndon Arrays Simplified

Authors: Ellert, Jonas

Abstract | Document (869 KB) | BibTeX

Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty

Authors: Erlebach, Thomas ; de Lima, Murilo Santos ; Megow, Nicole ; Schlöter, Jens

Abstract | Document (816 KB) | BibTeX

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search

Authors: Esmer, Barış Can ; Kulik, Ariel ; Marx, Dániel ; Neuen, Daniel ; Sharma, Roohani

Abstract | Document (929 KB) | BibTeX

Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection

Authors: Ezra, Esther ; Sharir, Micha

Abstract | Document (760 KB) | BibTeX

Submodular Maximization Subject to Matroid Intersection on the Fly

Authors: Feldman, Moran ; Norouzi-Fard, Ashkan ; Svensson, Ola ; Zenklusen, Rico

Abstract | Document (887 KB) | BibTeX

There and Back Again: On Applying Data Reduction Rules by Undoing Others

Authors: Figiel, Aleksander ; Froese, Vincent ; Nichterlein, André ; Niedermeier, Rolf

Abstract | Document (1,166 KB) | BibTeX

Improved Search of Relevant Points for Nearest-Neighbor Classification

Authors: Flores-Velazco, Alejandro

Abstract | Document (865 KB) | BibTeX

Longest Cycle Above Erdős-Gallai Bound

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Sagunov, Danil ; Simonov, Kirill

Abstract | Document (806 KB) | BibTeX

Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters

Authors: Friggstad, Zachary ; Jamshidian, Mahya

Abstract | Document (709 KB) | BibTeX

Simple Worst-Case Optimal Adaptive Prefix-Free Coding

Authors: Gagie, Travis

Abstract | Document (551 KB) | BibTeX

Taming Graphs with No Large Creatures and Skinny Ladders

Authors: Gajarský, Jakub ; Jaffke, Lars ; Lima, Paloma T. ; Novotná, Jana ; Pilipczuk, Marcin ; Rzążewski, Paweł ; Souza, Uéverton S.

Abstract | Document (1,282 KB) | BibTeX

Faster Path Queries in Colored Trees via Sparse Matrix Multiplication and Min-Plus Product

Authors: Gao, Younan ; He, Meng

Abstract | Document (755 KB) | BibTeX

Computing the 4-Edge-Connected Components of a Graph: An Experimental Study

Authors: Georgiadis, Loukas ; Italiano, Giuseppe F. ; Kosinas, Evangelos

Abstract | Document (1,500 KB) | BibTeX

Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited

Authors: Gima, Tatsuya ; Ito, Takehiro ; Kobayashi, Yasuaki ; Otachi, Yota

Abstract | Document (890 KB) | BibTeX

Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs

Authors: Goetze, Miriam ; Jungeblut, Paul ; Ueckerdt, Torsten

Abstract | Document (869 KB) | BibTeX

Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings

Authors: Haepler, Bernhard ; Hershkowitz, D. Ellis ; Zuzic, Goran

Abstract | Document (813 KB) | BibTeX

Hedonic Games and Treewidth Revisited

Authors: Hanaka, Tesshu ; Lampis, Michael

Abstract | Document (785 KB) | BibTeX

Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs

Authors: Henzinger, Monika ; Paz, Ami ; Sricharan, A. R.

Abstract | Document (935 KB) | BibTeX

O(1) Steiner Point Removal in Series-Parallel Graphs

Authors: Hershkowitz, D. Ellis ; Li, Jason

Abstract | Document (1,045 KB) | BibTeX

Chromatic k-Nearest Neighbor Queries

Authors: van der Horst, Thijs ; Löffler, Maarten ; Staals, Frank

Abstract | Document (1,119 KB) | BibTeX

Maximum Weight b-Matchings in Random-Order Streams

Authors: Huang, Chien-Chung ; Sellier, François

Abstract | Document (727 KB) | BibTeX

Embedding Phylogenetic Trees in Networks of Low Treewidth

Authors: van Iersel, Leo ; Jones, Mark ; Weller, Mathias

Abstract | Document (775 KB) | BibTeX

Vertex Sparsifiers for Hyperedge Connectivity

Authors: Jiang, Han ; Huang, Shang-En ; Saranurak, Thatchaphol ; Zhang, Tian

Abstract | Document (877 KB) | BibTeX

Approximation Algorithms for Round-UFP and Round-SAP

Authors: Kar, Debajyoti ; Khan, Arindam ; Wiese, Andreas

Abstract | Document (910 KB) | BibTeX

Optimizing Safe Flow Decompositions in DAGs

Authors: Khan, Shahbaz ; Tomescu, Alexandru I.

Abstract | Document (1,287 KB) | BibTeX

Scheduling Kernels via Configuration LP

Authors: Knop, Dušan ; Koutecký, Martin

Abstract | Document (774 KB) | BibTeX

Abstract Morphing Using the Hausdorff Distance and Voronoi Diagrams

Authors: de Kogel, Lex ; van Kreveld, Marc ; Vermeulen, Jordi L.

Abstract | Document (751 KB) | BibTeX

Average Sensitivity of the Knapsack Problem

Authors: Kumabe, Soh ; Yoshida, Yuichi

Abstract | Document (735 KB) | BibTeX

Cardinality Estimation Using Gumbel Distribution

Authors: Łukasiewicz, Aleksander ; Uznański, Przemysław

Abstract | Document (943 KB) | BibTeX

(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling

Authors: Maack, Marten ; Pukrop, Simon ; Rasmussen, Anna Rodriguez

Abstract | Document (749 KB) | BibTeX

Localized Geometric Moves to Compute Hyperbolic Structures on Triangulated 3-Manifolds

Authors: Maria, Clément ; Rouillé, Owen

Abstract | Document (1,027 KB) | BibTeX

Computing Treedepth in Polynomial Space and Linear FPT Time

Authors: Nadara, Wojciech ; Pilipczuk, Michał ; Smulewicz, Marcin

Abstract | Document (914 KB) | BibTeX

The Pareto Cover Problem

Authors: Natura, Bento ; Neuwohner, Meike ; Weltge, Stefan

Abstract | Document (754 KB) | BibTeX

A Unified Framework for Hopsets

Authors: Neiman, Ofer ; Shabat, Idan

Abstract | Document (757 KB) | BibTeX

Data Structures for Node Connectivity Queries

Authors: Nutov, Zeev

Abstract | Document (818 KB) | BibTeX

Improved Bounds for Online Balanced Graph Re-Partitioning

Authors: Rajaraman, Rajmohan ; Wasim, Omer

Abstract | Document (710 KB) | BibTeX

An Empirical Evaluation of k-Means Coresets

Authors: Schwiegelshohn, Chris ; Sheikh-Omar, Omar Ali

Abstract | Document (948 KB) | BibTeX

An Improved Algorithm for Finding the Shortest Synchronizing Words

Authors: Szykuła, Marek ; Zyzik, Adam

Abstract | Document (832 KB) | BibTeX

Fast RSK Correspondence by Doubling Search

Authors: Tiskin, Alexander

Abstract | Document (711 KB) | BibTeX

Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold

Authors: Walzer, Stefan

Abstract | Document (736 KB) | BibTeX

ParGeo: A Library for Parallel Computational Geometry

Authors: Wang, Yiqiu ; Yesantharao, Rahul ; Yu, Shangdi ; Dhulipala, Laxman ; Gu, Yan ; Shun, Julian

Abstract | Document (1,222 KB) | BibTeX

Combining Predicted and Live Traffic with Time-Dependent A* Potentials

Authors: Werner, Nils ; Zeitz, Tim

Abstract | Document (2,335 KB) | BibTeX

Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings

Authors: Xi, Zoe ; Kuszmaul, William

Abstract | Document (740 KB) | BibTeX

Correlated Stochastic Knapsack with a Submodular Objective

Authors: Yang, Sheng ; Khuller, Samir ; Choudhary, Sunav ; Mitra, Subrata ; Mahadik, Kanak

Abstract | Document (886 KB) | BibTeX

Faster Algorithm for Unique (k,2)-CSP

Authors: Zamir, Or

Abstract | Document (650 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

30th Annual European Symposium on Algorithms (ESA 2022)