Talks and Poster Presentations (without Proceedings-Entry):
S. Bhore, J. Haunert, F. Klute, G. Li, M. Nöllenburg:
"Balanced Independent and Dominating Sets onColored Interval Graphs";
Talk: EuroCG,
Würzburg, Deutschland;
2020-03-16
- 2020-03-18.
English abstract:
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.
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_290119.pdf
Created from the Publication Database of the Vienna University of Technology.