On domination-type problems in graphs with bounded proper-thinness

BONOMO, FLAVIA; DE ESTRADA, DIEGO

Paris

Conferencia; European Chapter on Combinatorial Optimization (ECCO); 2013

In this paper we solve in polynomial time by dynamic programming many of the domination-type problems in the literature and their weighted versions, such as existence/minimum (weighted) independent dominating set, minimum (weighted) total dominating set, minimum perfect dominating set and existence/minimum (weighted) efficient dominating set, for the class of graphs with bounded proper-thinness k, when the proper-k-thin representation of the graph is given.