Price of connectivity of graph parameters

• Název práce v češtině: Cena souvislosti grafových parametrů
• Název v anglickém jazyce: Price of connectivity of graph parameters
• Klíčová slova: cena souvislosti, grafový parametr
• Klíčová slova anglicky: price of connectivity, graph parameter
• Akademický rok vypsání: 2018/2019
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: Mgr. Tereza Klimošová, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 09.09.2019
• Datum zadání: 10.09.2019
• Datum potvrzení stud. oddělením: 01.11.2019
• Datum a čas obhajoby: 14.09.2020 08:30
• Datum odevzdání elektronické podoby: 30.07.2020
• Datum odevzdání tištěné podoby: 30.07.2020
• Datum proběhlé obhajoby: 14.09.2020
• Oponenti: Carl Feghali, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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.