Some Rainbow Problems in Graphs Have Complexity Equivalent to Satisfiability Problems - Département Informatique et Réseaux Accéder directement au contenu
Article Dans Une Revue International Transactions in Operational Research Année : 2022

Some Rainbow Problems in Graphs Have Complexity Equivalent to Satisfiability Problems

Résumé

In a vertex-coloured graph, a set of vertices S is said to be a rainbow set if every colour in the graph appears exactly once in S. We investigate the complexities of various problems dealing with domination in vertex-coloured graphs (existence of rainbow dominating sets, of rainbow locating-dominating sets, of rainbow identifying sets), including when we ask for a unique solution: we show equivalence between these complexities and those of the well-studied Boolean satisfiability problems.
Fichier principal
Vignette du fichier
OH-AL-TROPical.pdf (285.71 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02916921 , version 1 (30-11-2020)

Identifiants

  • HAL Id : hal-02916921 , version 1

Citer

Olivier Hudry, Antoine Lobstein. Some Rainbow Problems in Graphs Have Complexity Equivalent to Satisfiability Problems. International Transactions in Operational Research, 2022, 29 (3), pp.1547-1572. ⟨hal-02916921⟩
272 Consultations
140 Téléchargements

Partager

Gmail Facebook X LinkedIn More