| Accepted Papers | |
| Mateus de Oliveira Oliveira: A Slice Theoretic Approach for Embedding Problems on Digraphs | |
| Kenjiro Takazawa: Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs | |
| Guy Kortsarz and Zeev Nutov: Approximating Source Location and Star Survivable Network Problems | |
| Bernhard Bliem and Stefan Woltran: Complexity of Secure Sets | |
| Janos Pach and Dömötör Pálvölgyi: Unsplittable coverings in the plane | |
| Luis Pedro Montejano and Ignasi Sau: On the complexity of computing the k-restricted edge-connectivity of a graph | |
| Therese Biedl: Triangulating planar graphs while keeping the pathwidth small | |
| Eunjung Kim, Martin Milanic and Oliver Schaudt: Recognizing k-equistable graphs in FPT time | |
| Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen and Marcin Wrochna: Polynomial kernelization for removing induced claws and diamonds | |
| Serge Gaspers and Simon Mackenzie: On the Number of Minimal Separators in Graphs | |
| Mathieu Liedloff, Pedro Montealegre and Ioan Todinca: Beyond classes of graphs with ``few'' minimal separators: FPT results through potential maximal cliques | |
| Christophe Crespelle, Anthony Perez and Ioan Todinca: An O(n²) time Algorithm for the Minimal Permutation Completion Problem | |
| Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine and Takeaki Uno: A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs | |
| Mamadou Moustapha Kanté, Fatima Zahra Moataz, Benjamin Momège and Nicolas Nisse: Finding paths in grids with forbidden transitions | |
| Felix Joos: Parity linkage and the Erdős-Pósa property of odd cycles through prescribed vertices in highly connected graphs | |
| 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 | |
| Péter Hajnal, Alexander Igamberdiev, Günter Rote and André Schulz: Saturated simple and 2-simple topological graphs with few edges | |
| William S. Evans, Giuseppe Liotta and Fabrizio Montecchiani: Simultaneous Visibility Representations of Plane st-graphs Using L-shapes | |
| Andreas Brandstadt, Elaine M. Eschen and Erik Friese: Efficient Domination for Some Subclasses of P6-Free Graphs in Polynomial Time | |
| Thiago Marcilon and Rudini Sampaio: The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results | |
| Carsten Grimm: Efficient Farthest-Point Queries in Two-Terminal Series-Parallel Networks | |
| Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz and Konstantinos Stavropoulos: Colouring and Covering Nowhere Dense Graphs | |
| Bart M.P. Jansen: On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT | |
| Rémy Belmonte, Yota Otachi and Pascal Schweitzer: Induced Minor Free Graphs: Isomorphism and Clique-width | |
| Vadim Lozin, Igor Razgon and Viktor Zamaraev: Well-quasi-ordering does not imply bounded clique-width | |
| 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 | |
| Md. Jawaherul Alam, Stephen G. Kobourov, Sergey Pupyrev and Jackson Toeniskoetter: Weak Unit Disk and Interval Representation of Graphs | |
| Seok-Hee Hong and Hiroshi Nagamochi: Testing Full Outer-2-Planarity in Linear Time | |
| 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 | |
| Feodor Dragan and Arne Leitert: Minimum Eccentricity Shortest Paths in some Structured Graph Classes | |
| Peter Biro, Walter Kern, Daniel Paulusma and Peter Wojuteczky: The Stable Fixtures Problem with Payments | |
| 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 | |
| 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 | |
Pictures and Videos of WG 2015
 |
|
|
Opening Addresses |
|
 |
 |
| TUM SVP Hans Pongratz (PDF) | IN Dean H.-J. Bungartz |
| Videos |
 |
 |
 |
|
Invited Talk: Daniël Paulusma "Open Problems on Graph Coloring for Special Graph Classes" |
Invited Talk: Shmuel Zaks "On the Complexity of Approximation and On-line Scheduling Problems with Applications to Optical Networks" |
Invited Talk: Rolf Niedermeier "Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics" |
|
Recording (mp4, 731 MB) |
Recording (mp4, 805 MB) |
Recording (mp4, 949 MB) |
| Session 1: Computational Complexity I |
||||
 |
 |
|||
| Bernhard Bliem | Simon Mackenzie | |||
| Session 2: Design and Analysis | ||||
 |
 |
 |
||
| Feodor Dragan | Zeev Nutov | Ignasi Sau | ||
| Session 3: Computational Geometry |
||||
 |
 |
 |
 |
|
| Stephen G. Kobourov | Fabrizio Montecchiani | Balázs Keszegh | Dömötör Pálvölgyi | |
| Session 4: Structural Graph Theory I | ||||
 |
 |
 |
 |
 |
| Yota Otachi | Mateus de Oliveira Oliveira | Konstantinos Stavropoulos | Felix Joos | Kenjiro Takazawa |
| Session 5: Computational Complexity II |
||||
 |
 |
 |
 |
|
| Erik Friese | Takeaki Uno | Christophe Crespelle | Fatima Zahra Moataz | |
| Session 6: Graph Drawing | ||||
 |
 |
|||
| André Schulz | Seok-Hee Hong | |||
| Session 7: Fixed Parameter Tractability I |
||||
 |
 |
|||
| Therese Biedl | Florent Foucaud | |||
| Session 8: Computational Complexity III | ||||
 |
 |
 |
 |
|
| Walter Kern | Tomáš Valla | Carsten Grimm | Luís Felipe Cunha | |
| Session 9: Structural Graph Theory II |
||||
 |
 |
|||
| Fernanda Couto | Igor Razgon | |||
| Session 10: Fixed Parameter Tractability II | ||||
 |
 |
 |
 |
|
| Erik Jan van Leeuwen | Bart M.P. Jansen | Oliver Schaudt | Pedro Montealegre | |
