Complexity of Unique (Optimal) Solutions in Graphs: Vertex Cover and Domination - Equipe Mathématiques discrètes, codage et cryptographie Accéder directement au contenu
Article Dans Une Revue Journal of Combinatorial Mathematics and Combinatorial Computing Année : 2019

Complexity of Unique (Optimal) Solutions in Graphs: Vertex Cover and Domination

Olivier Hudry
Antoine Lobstein

Résumé

We study the complexity of four decision problems dealing with the uniqueness of a solution in a graph: "Uniqueness of a Vertex Cover with bounded size"(U-VC) and "Uniqueness of an Optimal Vertex Cover"(U-OVC), and for any fixed integer r ≥ 1, "Uniqueness of an r-Dominating Code with bounded size" (U-DCr) and "Uniqueness of an Optimal r-Dominating Code" (U-ODCr). In particular, we give a polynomial reduction from "Unique Satisfiability of a Boolean formula" (U-SAT
Fichier principal
Vignette du fichier
OH-AL-VCandDom.pdf (231.25 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : hal-01613388 , version 1

Citer

Olivier Hudry, Antoine Lobstein. Complexity of Unique (Optimal) Solutions in Graphs: Vertex Cover and Domination. Journal of Combinatorial Mathematics and Combinatorial Computing, 2019, 110, pp.217-240. ⟨hal-01613388⟩
277 Consultations
208 Téléchargements

Partager

Gmail Facebook X LinkedIn More