Combinatorial and algorithmic aspects of identifying codes in graphs
type: Dataset
description: We study combinatorial and algorithmic aspects of identifying codes in graphs. An identifying code is a set of vertices of a graph such that, on the one hand, each vertex out of the code has a neighbour in the code, and, on the other hand, all vertices have a distinct neighbourhood within the code. We characterize those graphs and digraphs that reach the known upper bounds on the minimum size of an identifying code. We also give new lower and upper bounds on this parameter for graphs of given maximum degree, graphs of girth at least 5, interval graphs and line graphs. Further, we study the computational complexity of the decision and optimization problems associated with the notion of an identifying code. We show that these problems remain computationally difficult, even when restricted to bipartite, co-bipartite, split, interval or line graphs. Finally, we give a \textsf{PTAS} algorithm for unit interval graphs.
issued: 2026-05-30T15:20:30.716182
language: en
modified: 2026-05-30T15:20:30.716189
contact point: Organization
  fn: CCSD
keyword: algorithme-dapproximation
keyword: approximation-algorithm
keyword: code-identifiant
keyword: dominating-set
keyword: ensemble-dominant
keyword: graph-theory
keyword: identifying-code
keyword: infoeu-reposemanticsdoctoralthesis
keyword: infoinfo-cccomputer-science-cscomputational-complexity-cscc
keyword: infoinfo-dscomputer-science-csdata-structures-and-algorithms-csds
keyword: mathmath-comathematics-mathcombinatorics-mathco
keyword: np-completeness
keyword: np-completude
keyword: theorie-des-graphes
keyword: theses
landing page: https://theses.hal.science/tel-00766138

Combinatorial and algorithmic aspects of identifying codes in graphs
type: Distribution
format: HTML
issued: 2026-05-30T15:20:30.859058
modified: 2026-05-30T15:20:30.659290
access URL: https://theses.hal.science/tel-00766138

test_moissonnage_selune
type: Agent