 |
Journal articles
Complexity of Unique (Optimal) Solutions in Graphs: Vertex Cover and Domination
Abstract : 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
https://hal.archives-ouvertes.fr/hal-01613388
Contributor : Antoine Lobstein Connect in order to contact the contributor
Submitted on : Monday, November 30, 2020 - 1:03:50 PM
Last modification on : Monday, January 24, 2022 - 11:43:20 AM
Long-term archiving on: : Monday, March 1, 2021 - 6:59:38 PM
Contributor : Antoine Lobstein Connect in order to contact the contributor
Submitted on : Monday, November 30, 2020 - 1:03:50 PM
Last modification on : Monday, January 24, 2022 - 11:43:20 AM
Long-term archiving on: : Monday, March 1, 2021 - 6:59:38 PM
File
OH-AL-VCandDom.pdf
Files produced by the author(s)