Graph Decompositions: Small Width, Big Challenges 2020
- Rescheduled -
20 - 24 April 2020
Venue: Oort
If you are invited or already registered for this workshop, you have received login details by email.This workshop has been rescheduled to 22 - 26 March 2021
Description
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.
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
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
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
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
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
