Get all the updates for this publication
Given a vertex-coloured graph, a dominating set is said to be tropical if every colour of the graph appears at least once in the set. Here, we study minimum tropical dominating sets from structural and algorithmic points of view. First, we prove that the tropical dominating set problem is NP-complete even when restricted to a simple path. Last, we give approximability and inapproximability results for general and restricted classes of graphs, and establish a FPT algorithm for interval graphs.
View more info for "Tropical Dominating Sets in Vertex-Coloured Graphs"
Journal | Data powered by TypesetInternational Workshop on Algorithms and Computation |
---|---|
Publisher | Data powered by TypesetSpringer International Publishing |
Open Access | No |