User Tools

Site Tools


teaching:ss21:lab-ca

Lab Computational Analytics – Algorithms on tree-like graphs

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

Dates and Organization

You need a CS account from GSG to use Gitlab, BBB or overleaf (all hosted by the GSG). You can apply for it here.

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:

Week Date
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

Literature

For preparation, we suggest reading the following papers:

Tree-width

Max Cut

  • Bodlaender, Hans L., and Klaus Jansen. "On the complexity of the maximum cut problem." Annual Symposium on Theoretical Aspects of Computer Science. Springer, Berlin, Heidelberg, 1994. (Relevant is only the chapter „Graphs with bounded treewidth“; depending on the version of the paper it is chaper 3.2, 5.2 or 6.)

OGDF

  • Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, Petra Mutzel: The Open Graph Drawing Framework (OGDF). Chapter 17 in: R. Tamassia (ed.), Handbook of Graph Drawing and Visualization, CRC Press, 2014.
  • Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, Petra Mutzel: The Open Graph Drawing Framework. (abstract)

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.

teaching/ss21/lab-ca.txt · Last modified: 2021/04/29 14:49 by christine.dahn

Page Tools