All talks are available here.
Invited Talks
- Susanne Albers [Humboldt-Universität zu Berlin, Germany]
Title: Algorithms for Online Bipartite Matching
Abstract: We study the online version of the classical bipartite matching problem. In this setting one vertex set of a bipartite graph is given initially. The vertices of the second set arrive online. Each incoming vertex may be matched to an eligible partner vertex immediately upon arrival. The framework was initially introduced by Karp, Vazirani and Vazirani (STOC 1990) and has recently received considerable research interest due to its relevance in online advertising. In this talk we survey important contributions that have been developed in the algorithms community over the past years. The results address the standard problem setting as well as budgeted versions and scenarios with stochastic input.
- Andreas Brandstädt [University of Rostock, Germany]
Title: On the complexity of some packing and covering problems in graphs and hypergraphs
Abstract: Packing and covering problems in graphs and hypergraphs and their relationships belong to the most fundamental topics in combinatorics and graph algorithms and have a wide spectrum of applications in computer science, operations research and many other fields. Recently, there has been an increasing interest in graph and hypergraph problems combining packing and covering properties, and the NP-complete Exact Cover problem on hypergraphs is a good example. Closely related graph problems are the Efficient Domination and Efficient Edge Domination problems. We give a survey on existing results, describe some connections to other problems such as Maximum Weight Independent Set and Minimum Weight Dominating Set, consider some new cases where the problems are efficiently solvable by using structural properties of graph classes and using closure properties under the square operation, and we also extend the graph problems to hypergraphs.
- Saket Saurabh [Institute of Mathematical Sciences, India & University of Bergen, Norway]
Title: Matroids, Randomness and FPT Algorithms
Abstract: This talk will be dedicated to the recent developments in designing randomized
paramterized algorithms using techniques and tools from matroid theory.
Titles of all the talks of GROW 2013
- Susanne Albers: Algorithms for Online Bipartite Matching
- Andreas Brandstädt: On the complexity of some packing and covering problems in graphs and hypergraphs
- Saket Saurabh: Matroids, Randomness and FPT Algorithms
- Bruno Courcelle: Graph algorithms based on infinite automata: logical descriptions and usable constructions
- Marek Cygan: Improved approximation for 3-dimensional matching via bounded pathwidth local search
- Jiří Fiala: Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- Robert Ganian: Meta-Kernelization with Structural Parameters
- Alexander Grigoriev: Bidimensionality on geometric intersection graphs
- Qianping Gu: Practical algorithms for branch-decompositions and grad-minors of planar graphs
- Michel Habib: Graph Searches and cocomparability graphs
- Frédéric Havet: Finding a subdivision of a digraph
- Mamadou Kanté: On the linear rank-width of trees
- Stavros Kolliopoulos: Integrality gaps for strengthened LP relaxations of Capacitated and Lower-Bounded Facility Location
- Chun-Hung Liu: Structural theorems and well-quasi-ordering
- Daniel Lokshtanov: Independent Set in P5-Free Graphs in Polynomial Time
- Vadim Lozin: Minimal classes of graphs of unbounded clique-width
- George Mertzios: The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
- Martin Milanič: Graphs of Power-Bounded Clique-Width
- Christophe Paul: Explicit Linear Kernels via Dynamic Programming
- Marcin Pilipczuk: The planar directed k-Vertex Disjoint Paths problem is fixed-parameter tractable
- Michał Pilipczuk: Topological problems on tournaments
- Leonidas Pitsoulis: Decomposition of Binary Signed-Graphic Matroids
- Maadapuzhi Sridharan Ramanujan: Cuts on Skew-Symmetric Graphs and Linear Time FPT algorithms
- Nicola Santoro: Graph Search with Immunity
- Ingo Schiermeyer: Rainbow connection and forbidden subgraphs
- Stefan Szeider: A SAT Approach to Clique-Width
- Nicolas Trotignon: The stable set problem is FPT in bull-free graphs
- Antonios Varvitsiotis: On the rank constrained Grothendieck constant of graphs and a new tree-width-like graph parameter
(*) Regular talks
(**) Invited talks