Graph Decompositions: Small Width, Big Challenges

- This workshop is cancelled -

20 - 24 April 2020

Venue: Lorentz Center@Oort

If you are registered for this workshop, you have received login details by email.

Computational problems on networks can often be solved by efficient algorithms on graph models of such networks. Many graph algorithms first decompose the graph into parts and stitch problem solutions for the parts back to a solution for the whole. This requires the interface between different parts of the decomposition to be highly structured and sufficiently small, as measured by the width of the decomposition. The workshop aims to identify open problems within fundamental and computational challenges for decomposition width measures. By bringing together researchers from both the fundamental and computational side of the spectrum, the workshop will investigate the bottlenecks to solve these open problems. The workshop focuses on the computation of width measures, connections to combinatorial optimization, and applications in algorithms for various width measures including treewidth, cliquewidth, and booleanwidth.

Read more...

    Monday April 20

    09:30-10:00       Registration

    10:00-10:15       Welcome by Lorentz Center

    10:15-10:30       Workshop welcome

    10:30-11:30       Survey talk

    11:30-12:00       Discussion of challenges and open problems

     

    12:00-13:30       Lunch@ Snellius restaurant

     

    13:30-14:30       Survey talk

    14:30-15:00       Discussion of challenges and open problems

    15:00-15:30       Coffee and tea break

    15:30-16:30       Survey talk

    16:30-17:00       Discussion of challenges and open problems

    17:00-                Wine and cheese welcome party

     

    The programme will be announced shortly.

    Tuesday April 21

    09:00-10:00        Survey talk

    10:00-10:30        Discussion of challenges and open problems

    10:30-11:00        Coffee and tea break

    11:00-12:00        Summary, sharpening, and selection of open problems, forming of groups

     

    12:00-13:30        Lunch@ Snellius restaurant

     

    13:30-15:00        Parallel work in groups (Groups can consider informal tutorials on their problem)

    15:00-15:30        Coffee and tea break

    15:30-17:00        Parallel work in groups

    17:00-                 Presentation

     

    The programme will be announced shortly.

    Wednesday April 22

    09:00-10:00        Tutorial talk

    10:00-10:30        Short progress update on group work

    10:30-11:00        Coffee and tea break

    11:00-12:00        Parallel work in groups

     

    12:00-13:30        Lunch@ Snellius restaurant

     

    13:30-15:00        Parallel work in groups

    15:30-16:00        Coffee and tea break

    16:00-17:00        Short communications of selected recent results

    17:00-                 Workshop dinner

     

    The programme will be announced shortly.

    Thursday April 23

    09:00-10:00        Tutorial talk

    10:00-10:30        Short progress update on group work

    10:30-11:00        Coffee and tea break

    11:00-12:00        Parallel work in groups

     

    12:00-13:30        Lunch@ Snellius restaurant

     

    13:30-15:00        Parallel work in groups

    15:00-15:30        Coffee and tea break

    15:30-18:00        Parallel work in groups

     

    The programme will be announced shortly.

    Friday April 24

    09:00-10:00        Detailed reports on Research Direction 1 and 2

    10:00-10:30        Coffee and tea break

    10:30-11:30        Detailed reports on Research Direction 3 and 4

    11:30-12:30        Tutorial talk

     

    12:30                    Lunch@ Snellius restaurant

     

    The programme will be announced shortly.
    Please log in to view the participants information...

    Fedor V. Fomin, University of Bergen  

    Stefan Kratsch, Humboldt-Universit├Ąt zu Berlin  

    Arie M.C.A. Koster, RWTH Aachen University  

    Erik Jan van Leeuwen, Utrecht University  


Tanja Uitbeijerse

+31 71 527 5582

uitbeijerse@lorentzcenter.nl

Follow us on: