Trees form a unique graph class for which many NP-hard problems can be solved in polynomial and often linear time. The property of how tree-like a graph is, was defined by Robertson and Seymour in 1983: the tree-width of a graph. The tree-width of a graph is defined by the smallest tree-decomposition of the graph.
For graphs with bounded tree-width many NP-hard problems (eg. the Max-Cut problem) can be solved in polynomial time. Given a tree-decomposition of a graph with a small (or constant) tree-width the Max-Cut can be calculated in linear time.
No prior knowledge of tree-decompositions or parameterized algorithms is required. The knowledge from the class Advanced Algorithms (WS 2020/21) is helpful, but not mandatory.
Keywords: Tree-width, Tree-decomposition, parameterized algorithms, Graph algorithms, Maximum Cut
The weekly meetings will be on Thursdays at 12:15.
The lab will be held completely in digital manner. We will use a web conference system (e.g. Zoom, or similar). Contact Christine Dahn to get the invitation link to the conference.
Attending the initial meeting on Wed. 07.04.2021 11:00 o'clock is mandatory for joining the lab.
If you are interested in joining this lab, write an email to christine.dahn [add] cs.uni-bonn.de until 31.03.2021.
In the first meeting we will give a short introduction to the topic of the Lab. Furthermore, all organizational questions will be answered. Official registration of the students to the lab can be done in the following weeks. The exact date until when the students need to be registered will be announced in a following meeting.
The following plan will be updated regularly:
|14||07.04.2021 at 11:00||Initial meeting|
|15||13.04.2021 at 16:00||Meeting: Chose 2 heuristics you are interested in|
|16||22.04.2021 at 12:15||individual short presentations 1|
|17||29.04.2021 at 12:15||individual short presentations 2 + OGDF|
|18||06.05.2021 at 12:15||OGDF setup|
|19||different meeting date|
|20||20.05.2021 at 12:15|
|21||no meeting / recess||Pentecost vacation week|
|22||different meeting date|
|23||10.06.2021 at 12:15|
|24||17.06.2021 at 12:15|
|25||24.06.2021 at 12:15|
|26||01.07.2021 at 12:15|
|27||08.07.2021 at 12:15|
|28||15.07.2021 at 12:15|
|29||22.07.2021 at 12:15||final presentation|
|33||16.08.2021||final report due|
For preparation, we suggest reading the following papers:
If you have problems accessing a paper due to a paywall, try connecting to Uni Bonn via VPN or SSH. Then most articles are available without a fee (or better yet, the Uni pays the fee). If that doesn't work, let me know.
To find different versions of an article, search the title and main author on google scholar. Click on “all X versions” below the article you are interested in (check title, authors and year) to see the different versions. Some versions are not protected by a paywall, eg. if the authors published it on their institutes website. Be careful thou, some versions are outdated and might differ to the latest version. On the other hand, other versions might explain some aspects of the paper in more detail.