Seminar on Computing, PhD in Computing. ALBCOM Seminar on Algorithms and Theory of Computation. Course: Algorithms on topologically structured graphs

https://computing.phd.upc.edu/en/esdeveniments/seminar-on-computing-phd-in-computing-albcom-seminar-on-algorithms-and-theory-of-computation-course-algorithms-on-topologically-structured-graphs
Seminar on Computing, PhD in Computing. ALBCOM Seminar on Algorithms and Theory of Computation. Course: Algorithms on topologically structured graphs
2017-03-27T10:00:00+02:00
2017-03-30T10:00:00+02:00

When

Mar 27, 2017 10:00 AM to Mar 30, 2017 10:00 AM (Europe/Madrid / UTC200)

Where

S215 (floor -2), Omega Building, Campus Nord, UP

Add event to calendar

ALBCOM Seminar on Algorithms and Theory of Computation
=================================================================
Course: Algorithms on topologically structured graphs

Dates: Monday, March 27 to Thursday March 30, 2017

Time: 10h00 to 13h00

Lecturer: Dimitrios M. Thilikos, AlGCo project, CNRS, LIRMM, France

Abstract: Structural theorems in graph theory indicate that several
combinatorial problems on graphs become tractable when their inputs
satisfy certain topological characteristics (i.e., planarity, tree-likeness,
minor exclusion). In this course we present core results and concepts in
structural graph theory and, based on them, we present core techniques of
algorithmic design on topologically structured graphs and well as their
applications to approximation algorithms and parameterized computation.

Program:

Monday:

  Well quasi orderings

  Graphs and surfaces

  Graphs decompositions

Tuesday:

  Parameterized algorithms

  Graphs and Logic

  Dynamic programming

Wednesday:

  Bidimensionality

  Kernelization

  Approximation Schemes

Thursday:

  Flat structures

  Irrelevant vertex technque

  Other algorithmic applications