Identification de sommets dans les graphes
type: Dataset
description: The work presented in this document deals with identifying codes in graphs. This notion, introduced in the late 1990's, models fault-detection problems in networks. An identifying code can be seen as a variant of the domination problem, with an additional constraint for identifying the vertices. Finding the minimum cardinality of such a code is an NP-difficult problem. The results presented herein deal with four topics. The first topic is related to regular structures (grids, cycles, hypercubes, products of cliques, Sierpiński graphs), for which some results on the minimum cardinality of a code (bounds and exact values) are presented. Then, algorithmic aspects are developed, one the one hand about polynomial algorithms designed for specific graph classes (trees, fasciagraphs), on the other hand about the approximability of the problem. Some structural questions are then addressed, namely the construction of extremal graphs, the construction of families of graphs admitting a code of small cardinality, and the structure (degrees, induced subgraphs, etc.) of graphs admitting such a code. Finally, a new variant of the problem is presented, that is adaptive identifying codes. This variant enables one to model a situation where we may take advantage of the dynamic aspect of the problem, and hope to query significantly less vertices than in the static case. In particular, we explicit in this document several links that relate identifying codes to other kind of structures, such as dominating sets, superimposed codes, projective planes, or Rényi search games.
issued: 2026-05-12T04:48:59.400504
language: fr
modified: 2026-05-12T04:48:59.400509
contact point: Organization
  fn: CCSD
keyword: codes-identifiants
keyword: combinatoire
keyword: combinatorics
keyword: detection-de-defaillances
keyword: discrete-mathematics
keyword: fault-detection
keyword: graph-theory
keyword: habilitation-a-diriger-des-recherches
keyword: identifying-codes
keyword: infoeu-reposemanticsother
keyword: mathematiques-discretes
keyword: spiautoengineering-sciences-physicsautomatic
keyword: theorie-des-graphes
landing page: https://theses.hal.science/tel-00803528

Identification de sommets dans les graphes
type: Distribution
format: HTML
issued: 2026-05-12T04:48:59.455688
modified: 2026-05-12T04:48:59.377460
access URL: https://theses.hal.science/tel-00803528

test_moissonnage_selune
type: Agent