Session 1 – 7 June 2021

Session 1.1 – Chairman: Henning Meyerhenke

• 9:50 – 10:00 Conference Opening
• 10:00 – 10:30 Ben Strasser and Tim Zeitz
  A Fast and Tight Heuristic for A* in Road Networks (10.4230/LIPIcs.SEA.2021.6)
• 10:30 – 11:00 Coline Gianfrotta, Vladimir Reinharz, Dominique Barth and Alain Denise
  A Graph-based Similarity Approach to Classify Recurrent Complex Motifs from their Context in RNA Structures (10.4230/LIPIcs.SEA.2021.19)
• 11:00 – 11:30 Gerth Stølting Brodal, Rolf Fagerberg, David Hammer, Ulrich Meyer, Manuel Penschuck and Hung Tran
  An Experimental Study of External Memory Algorithms for Connected Components (10.4230/LIPIcs.SEA.2021.23)
• 11:30 – 12:00 Samantha Chen and Yusu Wang
  Approximation algorithms for 1-Wasserstein distance between persistence diagrams (10.4230/LIPIcs.SEA.2021.14)

Session 1.2 – Chairman: Vincenzo Bonifaci

• 14:00 – 14:30 Loukas Georgiadis, Konstantinos Giannis, Giuseppe Italiano and Evangelos Kosinas
  Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice (10.4230/LIPIcs.SEA.2021.20)
• 14:30 – 15:00 Simon Puglisi and Bella Zhukova
  Document Retrieval Hacks (10.4230/LIPIcs.SEA.2021.12)
• 15:00 – 15:30 Max Franck and Sorrachai Yingchareonthawornchai
  Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity (10.4230/LIPIcs.SEA.2021.1)

Session 1.3 – Chairman: David Coudert

• 16:00 – 17:00  Invited Talk: Petra Mutzel
  Algorithmic Data Science

The area of algorithmic data science offers new opportunities for researchers in the algorithmic community. In this talk we will see examples that show that algorithm engineering is the perfect foundation for algorithmic data science. In my opinion, these opportunities should be exploited as this will be fruitful for both areas, algorithmics as well as data sciences. I would like to call for our community to participate more in algorithmic data science. Now we have the opportunity to shape this emerging field.

Session 2 – 8 June 2021

Session 2.1 – Chairman: Loukas Georgiadis

• 10:00 – 10:30 Patrick Dinklage, Johannes Fischer and Alexander Herlez
  Engineering Predecessor Data Structures for Dynamic Integer Sets (10.4230/LIPIcs.SEA.2021.7)
• 10:30 – 11:00 Mark Blacher, Joachim Giesen and Lars Kühne
  Fast and Robust Vectorized In-Place Sorting of Primitive Types (10.4230/LIPIcs.SEA.2021.3)
• 11:00 – 11:30 Thomas Bläsius, Tobias Friedrich and Maximilian Katzmann
  Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane (10.4230/LIPIcs.SEA.2021.22)
• 11:30 – 12:00 Frederic Cazals, Timothee O’Donnell and Bernard Delmas
  Fréchet mean and p-mean on the unit circle: decidability, algorithm, and applications to clustering on the flat torus (10.4230/LIPIcs.SEA.2021.15)

Session 2.2 – Chairman: Erwan Le Merrer

• 13:30 – 14:00 Miki Hermann
  How to Find the Exit from a 3-Dimensional Maze (10.4230/LIPIcs.SEA.2021.21)
• 14:00 – 14:30 Kevin Buchin, Sándor Fekete, Alexander Hill, Linda Kleist, Irina Kostitsyna, Dominik Krupke, Roel Lambers and Martijn Struijs
  Minimum Scan Cover and Variants - Theory and Experiments (10.4230/LIPIcs.SEA.2021.4)
• 14:30 – 15:00 Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov and Richard Spence
  Multi-level Weighted Additive Spanners (10.4230/LIPIcs.SEA.2021.16)
• 15:00 – 15:30 Tobias Heuer, Nikolai Maas and Sebastian Schlag
  Multilevel Hypergraph Partitioning with Vertex Weights Revisited (10.4230/LIPIcs.SEA.2021.8)

Session 2.3 – Chairman: Emanuele Natale

• 16:00 – 17:00 Invited Talk: Dominik Kempa
  How to store massive sequence collections in a searchable form

Compressed indexing is concerned with the design and construction of data structures to store massive sequences in space close to the size of compressed data, while simultaneously providing searching functionality (such as pattern matching) on the original uncompressed data. These indexes have a huge impact on the analysis of large-scale DNA databases (containing hundreds of thousands of genomes) but until recently the size of many indexes lacked theoretical guarantees and their construction remains a computational bottleneck.
In this talk I will describe my work proving theoretical guarantees on index size as a function of compressed data size, resolving a key open question in this field. Related to that, I will also describe new algorithms for converting between two conceptually distinct compressed representations, Lempel-Ziv and the Burrows-Wheeler Transform. I will show how these new findings enable advanced computation directly on compressed data. I will conclude by describing avenues for future work, including the new algorithms for the construction of compressed indexes that have the potential to cut indexing time by further orders of magnitude, unlocking the ability to search truly enormous text or DNA datasets.

Session 3 – 9 June 2021

Session 3.1 – Chairman: Laurent Viennot

• 10:00 – 10:30 Valentin Buchhold and Dorothea Wagner
  Nearest-Neighbor Queries in Customizable Contraction Hierarchies and Applications (10.4230/LIPIcs.SEA.2021.18)
• 10:30 – 11:00 Kathrin Hanauer, Christian Schulz and Jonathan Trummer
  O’Reach: Even Faster Reachability in Large Graphs (10.4230/LIPIcs.SEA.2021.13)
• 11:00 – 11:30 Marco Calamai, Pierluigi Crescenzi and Andrea Marino
  On Computing the Diameter of (Weighted) Link Streams (10.4230/LIPIcs.SEA.2021.11)
• 11:30 – 12:00 Ernst Althaus, Daniela Schnurbusch, Julian Wüschner and Sarah Ziegler
  On Tamaki’s Algorithm to Compute Treewidths 10.4230/LIPIcs.SEA.2021.9)

Session 3.2 – Chairman: Luca Becchetti

• 13:30 – 14:00 Louisa Ruixue Huang, Jessica Shi and Julian Shun
  Parallel Five-Cycle Counting Algorithms (10.4230/LIPIcs.SEA.2021.2)
• 14:00 – 14:30 Seungbum Jo, Wooyoung Park and Srinivasa Rao Satti
  Practical Implementation of Encoding Range Top-2 Queries (10.4230/LIPIcs.SEA.2021.10)
• 14:30 – 15:00 Demian Hespe, Sebastian Lamm and Christian Schorr
  Targeted Branching for the Maximum Independent Set Problem (10.4230/LIPIcs.SEA.2021.17)
• 15:00 – 15:30 Emmanuel Arrighi and Mateus De Oliveira Oliveira
  Three is Enough for Steiner Trees (10.4230/LIPIcs.SEA.2021.5)

Session 3.3 – Chairman: Emanuele Natale

• 16:00 – 17:00 Invited Talk: Blair D. Sullivan
  Putting parameterization into practice

The field of network science has burgeoned in the last two decades, developing new methods for analyzing complex network data of ever-increasing scale. Surprisingly, few approaches draw on the wealth of efficient algorithms arising from structural graph theory and parameterized complexity. In part, this is due to the primarily theoretical nature of the related literature, unrealistic structural assumptions, and a lack of cross-pollination of the research communities. In this talk, we survey the key ingredients for bridging this theory-practice gap, and describe several applications which demonstrate the potential of parameterized graph algorithms in computational genomics.