Thesis (Selection of subject)Thesis (Selection of subject)(version: 354)
Assignment details
   Login via CAS
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
Type of assignment: 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
Reviewers: Carl Feghali, Ph.D.
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.
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.
Charles University | Information system of Charles University |