Some Rainbow Problems in Graphs Have Complexity Equivalent to Satisfiability Problems - Equipe Cybersécurité et Cryptographie
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⟩
331 Consultations
195 Téléchargements

Partager

More