Algorithms and Data Structures -

. .

Résumé :
This book constitutes the refereed proceedings of the 18th International Symposium on Algorithms and Data Structures, WADS 2023, held during July 31-August 2, 2023. The 47 regular papers, presented in this book, were carefully reviewed and selected from a total of 92 submissions. They present original research on the theory, design and application of algorithms and data structures.

Sommaire:

Geometric Spanning Trees Minimizing the Wiener Index.- The Mutual Visibility Problem for Fat Robots.- Faster Algorithms for Cycle Hitting Problems on Disk Graphs.- Tight analysis of the lazy algorithm for open online dial-a-ride.- Online TSP with Known Locations.- Socially Fair Matching: Exact and Approximation Algorithms.- A Parameterized Approximation Scheme for Generalized Partial Vertex Cover.- Dominator Coloring and CD Coloring in Almost Cluster Graphs.- Tight Approximation Algorithms for Ordered Covering.- Online Minimum Spanning Trees with Weight Predictions.- Compact Distance Oracles with Large Sensitivity and Low Stretch.- Finding Diameter-Reducing Shortcuts in Trees.- Approximating the Smallest k-Enclosing Geodesic Disc in a Simple Polygon.- Online Interval Scheduling with Predictions.- On Length-Sensitive Frechet Similarity.- Hardness of Graph-Structured Algebraic and Symbolic Problems-. Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs.- Efficient k-center algorithms for planar points in convex position.- Classification via Two-Way Comparisons (extended abstract).- Improved Bounds for Discrete Voronoi Games.- General Space-Time Tradeoffs via Relational Queries.- Approximate Minimum Sum Colorings and Maximum k-Colorable Subgraphs of Chordal Graphs.- Differentially Private Range Query on Shortest Paths.- Revisiting Graph Persistence for Updates and Efficiency.- Block Crossings in One-Sided Tanglegrams.- Observation Routes and External Watchman Routes.- Lower Bounds for Non-Adaptive Shortest Path Relaxation.- Shortest coordinated motion for square robots.- Linear Layouts of Bipartite Planar Graphs.- Adaptive Data Structures for 2D Dominance Colored Range Counting.- Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent.- External-Memory Sorting with Comparison Errors.- Verifying the Product of Generalized Boolean Matrix Multiplication and Its Applications to Detect Small Subgraphs.- Reconfiguration of Time-Respecting Arborescences.- Algorithmic Theory of Qubit Routing.- 3-Coloring C4 or C3-free Diameter Two Graphs.- Colored Constrained Spanning Tree on Directed Graphs.- Geometric Hitting Set for Line-Constrained Disks.- An ETH-Tight Algorithm for Bidirected Steiner Connectivity.- From Curves to Words and Back Again: Geometric Computation of Minimum-Area Homotopy.- Fully dynamic clustering and diversity maximization in doubling metrics.- Quick Minimization of Tardy Processing Time on a Single Machine.- Space-Efficient Functional Offline-Partially-Persistent Trees with Applications to Planar Point Location.- Approximating the discrete center line segment in linear time.- Density Approximation for Moving Groups.- Dynamic Convex Hulls under Window-Sliding Updates.- Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs.