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 originale | Anglais |
|---|---|
| Pages (de - à) | 1547-1572 |
| Nombre de pages | 26 |
| journal | International Transactions in Operational Research |
| Volume | 29 |
| Numéro de publication | 3 |
| Les DOIs | |
| état | Publié - 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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver