Vorträge und Posterpräsentationen (ohne Tagungsband-Eintrag):
S. Bhore, J. Haunert, F. Klute, G. Li, M. Nöllenburg:
"Balanced Independent and Dominating Sets onColored Interval Graphs";
Vortrag: EuroCG,
Würzburg, Deutschland;
16.03.2020
- 18.03.2020.
Kurzfassung englisch:
We study two new versions of independent and dominating set problems on vertex-colored intervalgraphs, namelyf-Balanced Independent Set(f-BIS) andf-Balanced Dominating Set(f-BDS).LetG= (V,E)be a vertex-colored interval graph with ak-coloringγ:V→{1,...,k}for somek∈N. A subset of verticesS⊆Vis calledf-balancedifScontainsfvertices from each colorclass. In thef-BIS andf-BDS problems, the objective is to compute an independent set or adominating set that isf-balanced. We show that both problems areNP-complete even on properinterval graphs. For the BIS problem on interval graphs, we design twoFPTalgorithms, oneparameterized by(f,k)and the other by the vertex cover number ofG. Moreover, we present a2-approximation algorithm for a slight variation of BIS on proper interval graphs.
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_290119.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.