Price of connectivity of graph parameters

• Thesis title in Czech: Cena souvislosti grafových parametrů
• Thesis title in English: Price of connectivity of graph parameters
• Key words: cena souvislosti, grafový parametr
• English key words: price of connectivity, graph parameter
• Academic year of topic announcement: 2018/2019
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: Mgr. Tereza Klimošová, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 09.09.2019
• Date of assignment: 10.09.2019
• Confirmed by Study dept. on: 01.11.2019
• Date and time of defence: 14.09.2020 08:30
• Date of electronic submission: 30.07.2020
• Date of submission of printed version: 30.07.2020
• Date of proceeded defence: 14.09.2020
• Opponents: Carl Feghali, Ph.D.

Guidelines

Many graph substructures such as dominating set or vertex cover have a connected variant, where we add a requirement of connectivity of the substructure in question. This naturally leads to a notion of connected variants of graph parameters such as minimum connected dominating set etc. Interplay the parameter and its connected counterpart is studied from various algorithmic and structural aspects, often in terms of price of connectivity (ratio between the values of the connected and ordinary version of a parameter). The student will focus on open problems in the area.

References

Belmonte, Rémy, Pim van't Hof, Marcin Kamiński, and Daniël Paulusma. "The price of connectivity for feedback vertex set." Discrete Applied Mathematics 217 (2017): 132-143.

Camby, Eglantine. "Price of Connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs." Graphs and combinatorics 35.1 (2019): 103-118.

Camby, Eglantine, and Oliver Schaudt. "The price of connectivity for dominating set: Upper bounds and complexity." Discrete applied mathematics 177 (2014): 53-59.