Perugia, Italy
Program
Detailed Schedule #
Wednesday, March 4
| Time | Events |
|---|---|
| 09:00 — 10:00 | Session 1: Games and voting |
| 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 |
| 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 |
| 14:00 — 15:00 | Session 3: Invited talk |
| 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 |
| 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 |
| 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 |
Thursday, March 5
| Time | Events |
|---|---|
| 09:00 — 10:00 | Session 6: Invited talk |
| 09:00 — 10:00 |
P. Mutzel Graph Similarity: Concepts, Methods, and Challenges |
| 10:00 — 10:30 | Coffee break |
| 10:30 — 12:10 | Session 7: Complexity |
| 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 |
| 14:00 — 15:40 | Session 8: Approximation |
| 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 |
| 19:30 — 21:30 | Social dinner |
Friday, March 6
| Time | Events |
|---|---|
| 09:00 — 10:00 | Session 9: Invited talk |
| 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: Shortest paths and minimum spanning trees |
| 10:30 — 10:50 |
T. Gima, Y. Kobayashi, Y. Otachi, T. Sato Forcing a unique minimum spanning tree and a unique shortest path |
| 10:50 — 11:10 |
A. Jabal Ameli, F. Motiei, M. Saghafian On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum |
| 11:10 — 11:30 |
A. López Martínez, M. de Berg, F. Spieksma Disjoint Tours and the Price of Diversity |
| 11:30 — 11:50 |
T. Eom, T. Ahn, M. Song, H.-K. Ahn Shortcutting the diameter of a polygon |
| 11:50 — 12:10 |
R. Saito, T. Ito Parameterized Complexity of Reconfiguring Vertex-Disjoint Shortest Paths |
| 12:10 — 14:00 | Lunch |
| 14:00 — 15:40 | Session 11: Geometric problems |
| 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 |
| 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 |