| Schedule |
| Locations |
|
| Maps: Garching near Munich Map TUM Computer Science Campus Garching | |
| All Talks: Leibniz Rechenzentrum (LRZ), Lecture Room H.E. 009 |
| Tuesday, June 16 |
|
| 18:30-21:00 | Welcome Reception (Mathematics / Computer Science Building) |
| Wednesday, June 17 |
||
| 08:30-08:45 | Conference Welcome TUM SVP Hans Pongratz IN Dean H.-J. Bungartz |
|
| 08:45-09:45 | Invited Talk: Daniël Paulusma "Open Problems on Graph Coloring for Special Graph Classes" |
|
| 09:45-10:35 | Session 1: Computational Complexity I Chair: Pinar Heggernes |
|
| 09:45-10:10 | Bernhard Bliem and Stefan Woltran: Complexity of Secure Sets | |
| 10:10-10:35 | Serge Gaspers and Simon Mackenzie: On the Number of Minimal Separators in Graphs | |
| 10:35-11:00 | Coffee Break | |
| 11:00-12:15 | Session 2: Design and Analysis Chair: Jan van Leeuwen |
|
| 11:00-11:25 | Feodor Dragan and Arne Leitert: Minimum Eccentricity Shortest Paths in Some Structured Graph Classes | |
| 11:25-11:50 | Guy Kortsarz and Zeev Nutov: Approximating Source Location and Star Survivable Network Problems | |
| 11:50-12:15 | Luis Pedro Montejano and Ignasi Sau: On the Complexity of Computing the k-restricted edge-connectivity of a Graph | |
| 12:15-14:00 | Lunch Break | |
| 14:00-15:40 | Session 3: Computational Geometry Chair: Michael Kaufmann |
|
| 14:00-14:25 | Md. Jawaherul Alam, Stephen G. Kobourov, Sergey Pupyrev and Jackson Toeniskoetter: Weak Unit Disk and Interval Representation of Graphs |
|
| 14:25-14:50 | William S. Evans, Giuseppe Liotta and Fabrizio Montecchiani: Simultaneous Visibility Representations of Plane st-graphs Using L-shapes | |
| 14:50-15:15 | Balázs Keszegh and Dömötör Pálvölgyi: An Abstract Approach to Polychromatic Coloring: Shallow Hitting Sets in ABA-free Hypergraphs and Pseudohalfplanes | |
| 15:15-15:40 | János Pach and Dömötör Pálvölgyi: Unsplittable Coverings in the Plane | |
| 15:40-16:05 | Coffee Break | |
| 16:05-18:10 | Session 4: Structural Graph Theory I Chair: Jan Kratochvil |
|
| 16:05-16:30 | Rémy Belmonte, Yota Otachi and Pascal Schweitzer: Induced Minor Free Graphs: Isomorphism and Clique-width | |
| 16:30-16:55 | Mateus de Oliveira Oliveira: A Slice Theoretic Approach for Embedding Problems on Digraphs | |
| 16:55-17:20 | Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz and Konstantinos Stavropoulos: Colouring and Covering Nowhere Dense Graphs | |
| 17:20-17:45 | Felix Joos: Parity Linkage and the Erdős-Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs | |
| 17:45-18:10 | Kenjiro Takazawa: Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs | |
| Thursday, June 18 |
||
| 08:30-10:10 | Session 5: Computational Complexity II Chair: Van Bang Le |
|
| 08:30-08:55 | Andreas Brandstadt, Elaine M. Eschen and Erik Friese: Efficient Domination for Some Subclasses of P6-Free Graphs in Polynomial Time | |
| 08:55-09:20 | Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine and Takeaki Uno: A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs | |
| 09:20-09:45 | Christophe Crespelle, Anthony Perez and Ioan Todinca: An O(n²) time Algorithm for the Minimal Permutation Completion Problem | |
| 09:45-10:10 | Mamadou Moustapha Kanté, Fatima Zahra Moataz, Benjamin Momège and Nicolas Nisse: Finding Paths in Grids with Forbidden Transitions | |
| 10:10-10:35 | Coffee Break | |
| 10:35-11:35 | Invited Talk: Shmuel Zaks "On the Complexity of Approximation and On-line Scheduling Problems with Applications to Optical Networks" | |
| 11:35-12:25 | Session 6: Graph Drawing Chair: Michael Kaufmann |
|
| 11:35-12:00 | Péter Hajnal, Alexander Igamberdiev, Günter Rote and André Schulz: Saturated Simple and 2-simple Topological Graphs with Few Edges | |
| 12:00-12:25 | Seok-Hee Hong and Hiroshi Nagamochi: Testing Full Outer-2-Planarity in Linear Time | |
| 12:25-14:00 | Lunch Break | |
| 14:00-14:50 | Session 7: Fixed Parameter Tractability I Chair: Hans Bodlaender |
|
| 14:00-14:25 | Therese Biedl: Triangulating Planar Graphs while Keeping the Pathwidth Small | |
| 14:25-14:50 | Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau and Petru Valicov: Algorithms and Complexity for Metric Dimension and Location-Domination on Interval and Permutation Graphs | |
| 14:50-23:00 | Excursion and Conference Dinner | |
| Friday, June 19 |
||
| 08:30-10:10 | Session 8: Computational Complexity III Chair: Haiko Müller |
|
| 08:30-08:55 | Péter Biró, Walter Kern, Daniël Paulusma and Péter Wojuteczky: The Stable Fixtures Problem with Payments | |
| 08:55-09:20 | Ferdinando Cicalese, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyi and Tomáš Valla: On the Tree Search Problem with Non-uniform Costs | |
| 09:20-09:45 | Carsten Grimm: Efficient Farthest-Point Queries in Two-Terminal Series-Parallel Networks | |
| 09:45-10:10 | Thiago Marcilon and Rudini Sampaio: The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results | |
| 10:10-10:35 | Coffee Break | |
| 10:35-11:25 | Session 9: Structural Graph Theory II Chair: Christophe Paul |
|
| 10:35-11:00 | Fernanda Couto, Luerbio Faria, Sylvain Gravier, Sulamita Klein and Vinícius F. Dos Santos: On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs | |
| 11:00-11:25 | Vadim Lozin, Igor Razgon and Viktor Zamaraev: Well-quasi-ordering does not Imply Bounded Clique-width | |
| 11:25-12:25 | Invited Talk: Rolf Niedermeier "Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics" | |
| 12:25-14:00 | Lunch Break |
|
| 14:00-15:40 | Session 10: Fixed Parameter Tractability II Chair: Dieter Kratsch |
|
| 14:00-14:25 | Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen and Marcin Wrochna: Polynomial Kernelization for Removing Induced Claws and Diamonds | |
| 14:25-14:50 | Bart M.P. Jansen: On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT | |
| 14:50-15:15 | Eunjung Kim, Martin Milanic and Oliver Schaudt: Recognizing k-equi/ Graphs in FPT Time | |
| 15:15-15:40 | Mathieu Liedloff, Pedro Montealegre and Ioan Todinca: Beyond Classes of Graphs with ``few'' Minimal Separators: FPT Results through Potential Maximal Cliques | |
| 15:40 | End of Conference | |
