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:

Created from the Publication Database of the Vienna University of Technology.