Passer à la navigation principale Passer à la recherche Passer au contenu principal

Some rainbow problems in graphs have complexity equivalent to satisfiability problems

  • CNRS

Résultats de recherche: Contribution à un journalArticleRevue par des pairs

Résumé

In a vertex-colored graph, a set of vertices (Formula presented.) is said to be a rainbow set if every color in the graph appears exactly once in (Formula presented.). We investigate the complexities of various problems dealing with domination in vertex-colored graphs (existence of rainbow dominating sets, of rainbow locating-dominating sets, and 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.

langue originaleAnglais
Pages (de - à)1547-1572
Nombre de pages26
journalInternational Transactions in Operational Research
Volume29
Numéro de publication3
Les DOIs
étatPublié - 1 mai 2022

Empreinte digitale

Examiner les sujets de recherche de « Some rainbow problems in graphs have complexity equivalent to satisfiability problems ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation