Some rainbow problems in graphs have complexity equivalent to satisfiability problems

Autor: Olivier Hudry, Antoine Lobstein

Publikováno v: International Transactions in Operational Research
International Transactions in Operational Research, Wiley, 2022
International Transactions in Operational Research, 2022, 29 (3), pp.1547-1572
International Transactions in Operational Research, Wiley, In press
International Transactions in Operational Research, 2022

International audience; 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

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::34db5cada0407e2933c5f325244f2805
https://doi.org/10.1111/itor.12847

Unique (optimal) solutions: Complexity results for identifying and locating–dominating codes

Autor: Antoine Lobstein, Olivier Hudry

Publikováno v: Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2019, 767, pp.83-102. ⟨10.1016/j.tcs.2018.09.034⟩

International audience; We investigate the complexity of four decision problems dealing with the uniqueness of a solution in a graph: “Uniqueness of an r-Locating–Dominating Code with bounded size” (U-LDCr), “Uniqueness of an Optimal r-Locati

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dbb2e9e33492719e82693174c8d6f354
https://doi.org/10.1016/j.tcs.2018.09.034

The compared costs of domination, location-domination and identification

Autor: Olivier Hudry, Antoine Lobstein

Publikováno v: Discussiones Mathematicae Graph Theory, Vol 40, Iss 1, Pp 127-147 (2020)
Discussiones Mathematicae Graph Theory
Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2020, 40 (1), pp.127-147. ⟨10.7151/dmgt.2129⟩

International audience; Let G = (V, E) be a finite graph and r ≥ 1 be an integer. For v ∈ V , let B r (v) = {x ∈ V : d(v, x) ≤ r} be the ball of radius r centered at v. A set C ⊆ V is an r-dominating code if for all v ∈ V , we have B r (v

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0a9073f2bd839e7926901764b5bfea92
https://doi.org/10.7151/dmgt.2129

On the number of optimal identifying codes in a twin-free graph

Autor: Antoine Lobstein, Iiro S. Honkala, Olivier Hudry

Publikováno v: Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2015, 180, pp.111-119

Let G be a simple, undirected graph with vertex set? V . For v ? V and r ? 1 , we denote by B G , r ( v ) the ball of radius? r and centre? v . A set C ? V is said to be an r -identifying code in? G if the sets B G , r ( v ) ? C , v ? V , are all non

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::704c6813e2a3223bd78c4af66cc38a0b
https://doi.org/10.1016/j.dam.2014.08.020

Minimum sizes of identifying codes in graphs differing by one edge

Autor: Antoine Lobstein, Irène Charon, Olivier Hudry, Iiro S. Honkala

Publikováno v: Cryptography and Communications. 6:157-170

Let G be a simple, undirected graph with vertex set V. For v ? V and r ? 1, we denote by B G, r (v) the ball of radius r and centre v. A set 𝒞 ⊆ V ${\mathcal C} \subseteq V$ is said to be an r-identifying code in G if the sets B G , r ( v ) ? �

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::f7f2b2442444a094bdec536a1ae59b5f
https://doi.org/10.1007/s12095-013-0094-x