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 MackenzieOn 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 NutovApproximating Source Location and Star Survivable Network Problems
11:50-12:15 Luis Pedro Montejano and Ignasi SauOn 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 JoosParity 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 SampaioThe 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