Tropical Dominating Sets in Vertex-Coloured Graphs
| Autor: | Leandro Montero, Zsolt Tuza, Csilia Bujtás, Hakim El Maftouhi, Laurent Rosaz, N. Narayanan, Johan Thapper, Marek Karpinski, Yannis Manoussakis, Jean Alexandre Anglés D’Auriac |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Bidimensionality Combinatorics Indifference graph Pathwidth 010201 computation theory & mathematics Dominating set Independent set Maximal independent set Split graph Mathematics Distance-hereditary graph |
| Zdroj: | WALCOM: Algorithms and Computation ISBN: 9783319301389 WALCOM |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|