PROGRAM
Program at a Glance
| 10 May 2021 | 11 May 2021 | 12 May 2021 | |||
| 10:30 – 10:45 | Virtual Gathering (on Zoom) |
11:00-11:45 |
Invited Talk Katharina Huber |
11:00-11:45 |
Invited Talk Seffi Naor |
| 10:45 – 11:00 | WELCOME | ||||
| 11:00 – 11:45 | Invited Talk Henning Fernau | ||||
| 11:45 – 12:00 | Break | 11:45 – 12:00 | Break | 11:45 – 12:00 | Break |
| 12:00 – 13:00 | Session 1 (3×20’) GT&DO1 | 12:00-13:00 | Session 5 (3×20’) E&PC2 | 12:00 – 13:00 | Session 9 (3×20’) GA |
| 13:00 – 13:15 | Break | 13:00 – 13:15 | Break | 13:00 – 13:15 | Break |
| 13:15 – 14:15 | Session 2 (3×20’) OLA | 13:15 – 13:55 | Session 6 (2×20’) AA1 | 13:15 – 13:55 | Session 10 (2×20’) AA2 |
| 14:15 –15:30 | Lunch Break | 13:55 –15:30 | Lunch Break | 13:55 – 14:05 | CLOSING |
| 15:30 – 16:30 | Session 3 (3×20’) E&PC1 | 15:30 – 16:30 | Session 7 (3×20’) AACC2 | ||
| 16:30 – 16:45 | Break | 16:30 – 16:45 | Break | ||
| 16:45 – 17:25 | Session 4 (2×20’) AACC1 | 16:45 – 17:45 | Session 8 (3×20’) GT&DO2 |
All times are in Eastern European Summer Time (EEST)
(UTC +3)
Monday, 10 May 2021
10:30 – 10:45
10:45 – 11:00
11:00 – 11:45
Virtual Gathering (Zoom)
Welcome / Opening
Invited Talk – Henning Fernau:
Abundant Extensions
Chair: Tiziana Calamoneri
11:45 – 12:00
BREAK
12:00 – 13:00
Session 1 – Graph Theory & Discrete Optimization 1
Chair: Oleg Verbitsky
Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity
Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi and Yota Otachi
Three problems on well-partitioned chordal graphs
Jungho Ahn, Lars Jaffke, O-Joung Kwon and Paloma de Lima
On the Role of $3$’s for the 1-2-3 Conjecture
Julien Bensmail, Foivos Fioravantes and Fionn Mc Inerney
13:00 – 13:15
BREAK
13:15 – 14:15
Session 2 – Online Algorithms
Chair: Oleg Verbitsky
Online and approximate network construction from bounded connectivity constraints
Jesper Jansson, Christos Levcopoulos and Andrzej Lingas
Algorithms for Energy Conservation in Heterogeneous Data Centers
Susanne Albers and Jens Quedenfeld
Online Two-Dimensional Vector Packing with Advice
Bengt J. Nilsson and Gordana Vujovic
14:15 – 15:30
LUNCH BREAK
15:30 – 16:30
Session 3 – Exact and Parametrized Computation 1
Chair: Bengt Nilsson
FPT and kernelization algorithms for the Induced Tree problem
Guilherme de Castro Mendes Gomes, Vinicius F. dos Santos, Murilo Da Silva and Jayme Szwarcfiter
Circumventing Connectivity for Kernelization
Pallavi Jain, Lawqueen Kanesh, Shivesh Kumar Roy, Saket Saurabh and Roohani Sharma
A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
Rajesh Chitnis
16:30 – 16:45
BREAK
16:45 – 17:25
Session 4 – Analysis of Algorithms and Computational Complexity 1
Chair: Bengt Nilsson
Can Local Optimality Be Used for Efficient Data Reduction?
Christian Komusiewicz and Nils Morawietz
Fragile Complexity of Adaptive Algorithms
Prosenjit Bose, Pilar Cano, Rolf Fagerberg, John Iacono, Riko Jacob and Stefan Langerman
Tuesday, 11 May 2021
11:00 – 11:45
Invited Talk – Katharina Huber:
Phylogenetic Networks, A Way to Cope with Complex
Evolutionary Processes
Chair: Philipp Kindermann
11:45 – 12:00
BREAK
12:00 – 13:00
Session 5 – Exact and Parametrized Computation 2
Chair: Binh-Minh Bui-Xuan
The Parameterized Suffix Tray
Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
Aleksander Figiel, Anne-Sophie Himmel, André Nichterlein and Rolf Niedermeier
A Multistage View on 2-Satisfiability
Till Fluschnik
13:00 – 13:15
BREAK
13:15 – 13:55
Session 6 – Approximation Algorithms 1
Chair: Binh-Minh Bui-Xuan
The Multi-Budget Maximum Weighted Coverage Problem
Francesco Cellinese, Gianlorenzo D’Angelo, Gianpiero Monaco and Yllka Velaj
Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation
Louis Dublois, Michael Lampis and Vangelis Paschos
13:55 – 15:30
LUNCH BREAK
15:30 – 16:30
Session 7 – Analysis of Algorithms and Computational Complexity 2
Chair: Vinicius Dos Santos
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles
Barnaby Martin, Daniel Paulusma and Siani Smith
Distributed Distance-$r$ Covering Problems\\ on Sparse High-Girth Graphs
Saeed Akhoondian Amiri and Ben Wiederhake
Upper Tail Analysis of Bucket Sort and Random Tries
Ioana Bercea and Guy Even
16:30 – 16:45
BREAK
16:45 – 17:45
Session 8 – Graph Theory & Discrete Optimization 2
Chair: Vinicius Dos Santos
Globally rigid augmentation of minimally rigid graphs in R^2
Csaba Király and András Mihálykó
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties
Frank Fuhlbrück, Johannes Koebler, Ilia Ponomarenko and Oleg Verbitsky
Reconfiguration of Connected Graph Partitions via Recombination
Hugo Akitaya, Matias Korman, Oliver Korten, Diane Souvaine and Csaba Toth
Wednesday, 12 May 2021
11:00 – 11:45
Invited Talk – Joseph (Seffi) Naor:
Recent Advances in Competitive Analysis of Online
Algorithms
Chair: Guy Even
11:45 – 12:00
BREAK
12:00 – 13:00
Session 9 – Graph Algorithms (Computational Geometry and Graph Drawing)
Chair: Chryssis Georgiou
Covering a set of line segments with a few squares
Joachim Gudmundsson, Mees van de Kerkhof, André van Renssen, Frank Staals, Lionov Wiratma and Sampson Wong
Extending Partial Representations of Rectangular Duals with Given Contact Orientations
Jonathan Klawitter, Steven Chaplick, Philipp Kindermann, Ignaz Rutter and Alexander Wolff
On Vertex-Weighted Graph Realizations
Amotz Bar-Noy, Toni Böhnlein, David Peleg and Dror Rawitz
13:00 – 13:15
BREAK
13:15 – 13:55
Session 10 – Approximation Algorithms 2
Chair: Chryssis Georgiou
Throughput Scheduling with Equal Additive Laxity
Martin Böhm, Nicole Megow and Jens Schlöter
Temporal Matching on Geometric Graph Data
Timothé Picavet, Ngoc-Trung Nguyen and Binh-Minh Bui-Xuan
13:55 – 14:05
CLOSING