Talks

All talks  are available here.

 

Invited Talks

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.

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

  1. Susanne    Albers:    Algorithms for Online Bipartite Matching
  2. Andreas    Brandstädt:    On the complexity of some packing and covering problems in graphs and hypergraphs
  3. Saket    Saurabh:    Matroids, Randomness and FPT Algorithms
  4. Bruno    Courcelle:    Graph algorithms based on infinite automata: logical descriptions and usable constructions
  5. Marek     Cygan:    Improved approximation for 3-dimensional matching via bounded pathwidth local search
  6. Jiří    Fiala:    Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
  7. Robert    Ganian:    Meta-Kernelization with Structural Parameters
  8. Alexander     Grigoriev:    Bidimensionality on geometric intersection graphs
  9. Qianping    Gu:    Practical algorithms for branch-decompositions and grad-minors of planar graphs
  10. Michel    Habib:    Graph Searches and cocomparability graphs
  11. Frédéric    Havet:    Finding a subdivision of a digraph
  12. Mamadou    Kanté:    On the linear rank-width of trees
  13. Stavros    Kolliopoulos:    Integrality gaps for strengthened LP relaxations of Capacitated and Lower-Bounded Facility Location
  14. Chun-Hung    Liu:    Structural theorems and well-quasi-ordering
  15. Daniel    Lokshtanov:   Independent Set in P5-Free Graphs in Polynomial Time
  16. Vadim    Lozin:    Minimal classes of graphs of unbounded clique-width
  17. George     Mertzios:    The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
  18. Martin     Milanič:    Graphs of Power-Bounded Clique-Width
  19. Christophe    Paul:    Explicit Linear Kernels via Dynamic Programming
  20. Marcin     Pilipczuk:    The planar directed k-Vertex Disjoint Paths problem is fixed-parameter tractable
  21. Michał     Pilipczuk:    Topological problems on tournaments
  22. Leonidas    Pitsoulis:    Decomposition of Binary Signed-Graphic Matroids
  23. Maadapuzhi Sridharan     Ramanujan:   Cuts on Skew-Symmetric Graphs and Linear Time FPT algorithms
  24. Nicola     Santoro:    Graph Search with Immunity
  25. Ingo    Schiermeyer:    Rainbow connection and forbidden subgraphs
  26. Stefan    Szeider:    A SAT Approach to Clique-Width
  27. Nicolas    Trotignon:    The stable set problem is FPT in bull-free graphs
  28. Antonios    Varvitsiotis:    On the rank constrained Grothendieck constant of graphs and a new tree-width-like graph parameter

 

(*) Regular talks

(**) Invited talks