Port de NiceAntibes' City WallsBaie des Anges à Nice
SEA 2021 Université Côte d'Azur, Valrose, France
Nice's harbour.
SEA 2021 Université Côte d'Azur, Valrose, France
Antibes, 15 minutes by car from Sophia Antipolis
SEA 2021 Université Côte d'Azur, Valrose, France
Nice, la baie des Anges (Baia dei ange en niçois)


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.