Perugia, Italy
Program
Program Overview #
Time
Tue Mar 3
Wed Mar 4
Thu Mar 5
Fri Mar 6
08:00
08:30
09:00
09:30
10:00
10:30
11:00
11:30
12:00
12:30
13:00
13:30
14:00
14:30
15:00
15:30
16:00
16:30
17:00
17:30
18:00
18:30
19:00
19:30
20:00
20:30
21:00
21:30
Welcome Reception
18:30 — 20:30
18:30 — 20:30
On-site check-in
08:20 — 08:50
08:20 — 08:50
Session 1: Games and voting
09:00 — 10:00
09:00 — 10:00
Coffee break
10:00 — 10:30
10:00 — 10:30
Session 2: Graph drawings and embeddings
10:30 — 12:10
10:30 — 12:10
Lunch
12:10 — 14:00
12:10 — 14:00
Session 4: Graph reconfiguration
15:10 — 15:50
15:10 — 15:50
Coffee break
15:50 — 16:20
15:50 — 16:20
Session 5: Induced subgraphs and dominating sets
16:20 — 17:40
16:20 — 17:40
Business meeting
17:45 — 18:45
17:45 — 18:45
Coffee break
10:00 — 10:30
10:00 — 10:30
Session 7: Shortest paths and minimum spanning trees
10:35 — 12:15
10:35 — 12:15
Lunch
12:15 — 14:00
12:15 — 14:00
Session 8: Approximation
14:00 — 15:40
14:00 — 15:40
Excursion
16:00 — 19:00
16:00 — 19:00
Social dinner
19:30 — 21:30
19:30 — 21:30
Coffee break
10:00 — 10:30
10:00 — 10:30
Session 10: Complexity
10:30 — 12:10
10:30 — 12:10
Lunch
12:10 — 14:00
12:10 — 14:00
Session 11: Geometric problems
14:00 — 15:40
14:00 — 15:40
Coffee break
15:40 — 16:10
15:40 — 16:10
Session 12: Enumeration problems
16:10 — 17:30
16:10 — 17:30
Closing
17:30 — 17:45
17:30 — 17:45
Detailed Schedule #
Tuesday, March 3
| Time | Events |
|---|---|
| 18:30 — 20:30 | Welcome Reception Bar Pasticceria dell'Accademia (in the city center, Via dei Priori 52) |
Wednesday, March 4
| Time | Events |
|---|---|
| 08:20 — 08:50 | On-site check-in, Entrance to Aula Magna |
| 08:50 — 09:00 | Opening Aula Magna |
| 09:00 — 10:00 | Session 1: Games and voting — Chair: L. Grilli Aula Magna |
| 09:00 — 09:20 |
K. Burke, A. Dailly, N. Oijid Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles |
| 09:20 — 09:40 |
P. Arora, P. Dey, N. Misra Can One Flip Spoil It All? |
| 09:40 — 10:00 |
N. Kakimura and Y. Terai Computing Power Indices in Weighted Majority Games with Formal Power Series |
| 10:00 — 10:30 | Coffee break |
| 10:30 — 12:10 | Session 2: Graph drawings and embeddings — Chair: C. Binucci Aula Magna |
| 10:30 — 10:50 |
M. Chimani, M.H. Wagner Computing Beyond-Planar Crossing Numbers via Forbidden Crossing Patterns |
| 10:50 — 11:10 |
O. Aichholzer, Y. Higashikawa, J. Orthaber, D. Perz, B. Vogtenhuber, A. Weinberger Minimum-Weight Outerplane Laman Graphs |
| 11:10 — 11:30 |
S. van den Broek, M. van Kreveld, W. Meulemans, A. Simons Minimizing Vertical Length in Linked Bar Charts |
| 11:30 — 11:50 |
H. Förster, G. Ortali, L. Schlipf On Compaction and Realizability of Almost Convex Octilinear Representations |
| 11:50 — 12:10 |
M. Buchin, W. Kißler, F. Kubon Hardness and Parameterized Tractability of the Weak Graph Distance |
| 12:10 — 14:00 | Lunch, Campus Cafeteria (Mensa) |
| 14:00 — 15:00 | Session 3: Invited talk — Chair: G. Liotta Aula Magna |
| 14:00 — 15:00 |
P. Ferragina Data Compression and Indexing in the era of Machine Learning |
| 15:00 — 15:10 | Short break |
| 15:10 — 15:50 | Session 4: Graph reconfiguration — Chair: T. Saitoh Aula Magna |
| 15:10 — 15:30 |
H. Fernau, K. Mann How to Reconfigure Your Alliances |
| 15:30 — 15:50 |
J. Bensmail, N. Catherinot, F. Fioravantes, C. Marcille, N. Oijid Graph Irregularity via Edge Deletions |
| 15:50 — 16:20 | Coffee break |
| 16:20 — 17:40 | Session 5: Induced subgraphs and dominating sets — Chair: M. Saghafian Aula Magna |
| 16:20 — 16:40 |
H. Imamura, Y. Kobayashi, Y. Otachi, T. Saitoh, K. Sato, A. Takaoka, R. Yoshinaka, T. van der Zanden Finding Order-Preserving Subgraphs |
| 16:40 — 17:00 |
T. Hanaka, Y. Okada, Y. Otachi, L. Volk Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited |
| 17:00 — 17:20 |
M. D'Elia, F. Frati Large Induced Subgraphs of Bounded Degree in Outerplanar and Planar Graphs |
| 17:20 — 17:40 |
J. Kratochvíl, U. Bednarz, A. Michalski Complexity of perfect (1,2)-dominating sets in low-degree graphs |
| 17:45 — 18:45 | Business meeting Aula Magna |
Thursday, March 5
| Time | Events |
|---|---|
| 09:00 — 10:00 | Session 6: Invited talk — Chair: W. Didimo Aula Magna |
| 09:00 — 10:00 |
P. Mutzel Graph Similarity: Concepts, Methods, and Challenges |
| 10:00 — 10:30 | Coffee break |
| 10:30 — 10:35 | In Memoriam Prof. Hsu-Chun Yen |
| 10:35 — 12:15 | Session 7: Shortest paths and minimum spanning trees — Chair D. Perz Aula Magna |
| 10:35 — 10:55 |
T. Gima, Y. Kobayashi, Y. Otachi, T. Sato Forcing a unique minimum spanning tree and a unique shortest path |
| 10:55 — 11:15 |
A. Jabal Ameli, F. Motiei, M. Saghafian On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum |
| 11:15 — 11:35 |
A. López Martínez, M. de Berg, F. Spieksma Disjoint Tours and the Price of Diversity |
| 11:35 — 11:55 |
T. Eom, T. Ahn, M. Song, H.-K. Ahn Shortcutting the diameter of a polygon |
| 11:55 — 12:15 |
R. Saito, T. Ito Parameterized Complexity of Reconfiguring Vertex-Disjoint Shortest Paths |
| 12:15 — 14:00 | Lunch, Campus Cafeteria (Mensa) |
| 14:00 — 15:40 | Session 8: Approximation — Chair: F. Grosso Aula Magna |
| 14:00 — 14:20 |
S. Habib, D. Mondal, S. Sharmin, M.S. Rahman Hardness and Approximation Results for Extending Unique Neighborhood Networks |
| 14:20 — 14:40 |
M. Szyfelbein Approximating the Average-case Graph Search Problem with Non-uniform Costs |
| 14:40 — 15:00 |
D. Denisov, S. Dolev, D. Felmdan, M. Segal Linear time small coresets for k-mean clustering of segments with applications |
| 15:00 — 15:20 |
B. Auvray, J. David, R. Groult, T. Lecroq Cartesian Forest Matching |
| 15:20 — 15:40 |
M. Lohrey, L. Rische, L. Seelbach Benkner, J. Xochitemol Streaming algorithms for products of probabilities |
| 16:00 — 19:00 | Excursion (in the city center) |
| 19:30 — 21:30 | Social dinner Ristorante del Sole (in the city center, Via della Rupe 1) |
Friday, March 6
| Time | Events |
|---|---|
| 09:00 — 10:00 | Session 9: Invited talk — Chair: D. Mondal Aula Magna |
| 09:00 — 10:00 |
B. Jansen Sparsification and kernelization for constraint satisfaction problems through the lens of non-redundancy |
| 10:00 — 10:30 | Coffee break |
| 10:30 — 12:10 | Session 10: Complexity — Chair: F. Montecchiani Aula Magna |
| 10:30 — 10:50 |
L. Lehner, C. Komusiewicz, L.P. Staus A Complexity Analysis of the c-Closed Vertex Deletion Problem |
| 10:50 — 11:10 |
C. Bazgan, M. Chopin, A. Nichterlein, C. Richer On the Computational Complexity of Covering Multi-Interface Networks |
| 11:10 — 11:30 |
J. Bok, A. Das, A. Gujgiczer, N. Jedličková Generalizing Brooks' Theorem via Partial Coloring is Hard Classically and Locally |
| 11:30 — 11:50 |
S. S. Akhtar, P. Misra, G. Philip Space Efficient algorithms for parameterised problems |
| 11:50 — 12:10 |
M. Marin Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets |
| 12:10 — 14:00 | Lunch, Campus Cafeteria (Mensa) |
| 14:00 — 15:40 | Session 11: Geometric problems — Chair: E. Di Giacomo Aula Magna |
| Session sponsored by Tom Sawyer Software | |
| 14:00 — 14:20 |
N. Honorato-Droguett, K. Kurita, T. Hanaka, H. Ono, A. Wolff Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion |
| 14:20 — 14:40 |
K. Buchin, M. Buchin, J.E. Swiadek, S. Wong Fundamentals of Computing Continuous Dynamic Time Warping in 2D under Different Norms |
| 14:40 — 15:00 |
A. Rosenberg, E. Arkin, A. Efrat, O. Filtser, S. Kobourov, J. Kratochvíl, J. Mitchell The Gate-Cover Problem |
| 15:00 — 15:20 |
S.M.H. Kazemi, M.A. Abam, M. Ghodsi Trajectory Visibility at First Sight |
| 15:20 — 15:40 |
J. Friemel, D. Liedtke, C. Scheffer Tile Reconfiguration by a Finite Automaton |
| 15:40 — 16:10 | Coffee break |
| 16:10 — 17:30 | Session 12: Enumeration problems — Chair: A. Tappini Aula Magna |
| 16:10 — 16:30 |
R. Okuda, J. Kawahara, S.-i. Minato Enumerating All Graph Colorings Using Zero-Suppressed Binary Decision Diagrams |
| 16:30 — 16:50 |
M. D'Elia, I. Finocchi, M. Patrignani Engineering Algorithms for L-Isolated Maximal Clique Enumeration |
| 16:50 — 17:10 |
K. Kurita, K. Mann On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs |
| 17:10 — 17:30 |
Y. Nishimura, K. Haraguchi Enumeration of Bases in Matroid with Exponentially Large Ground Set |
| 17:30 — 17:45 | Closing Aula Magna |
