Combinatorial identification problems and graph powers - Archive ouverte HAL Access content directly
Theses Year : 2010

Combinatorial identification problems and graph powers

Problèmes d'identification combinatoire et puissances de graphes

(1)
1
David Auger
  • Function : Author
  • PersonId : 952013

Abstract

The thesis deals in a first with algorithmic and combinatorial properties of different variations on identifying codes in undirected graphs, a theoretical model for problems of detection and localization in networks. These issues led us to consider a notion of powers of graphs, which we then investigate into several directions.
Les codes identifiants dans les graphes modélisent des systèmes de détection et de localisation à distance de pannes multiples dans les réseaux. Nous abordons dans une première partie différents problèmes de nature algorithmique ou structurelle concernant plusieurs variations autour de ces codes ; en particulier, nous obtenons de nombreux résultats quant à la structure des graphes sans jumeaux. Ces questions nous amènent dans une deuxième partie à considérer une notion de puissance de graphe, que nous étudions plus avant. Nous obtenons en particulier des résultats de type extrémal et nous consacrons l'étude des racines carrées de graphes.
Fichier principal
Vignette du fichier
theseDA4Juin.pdf (1.8 Mo) Télécharger le fichier

Dates and versions

pastel-00593649 , version 1 (16-05-2011)

Identifiers

  • HAL Id : pastel-00593649 , version 1

Cite

David Auger. Problèmes d'identification combinatoire et puissances de graphes. Mathématique discrète [cs.DM]. Télécom ParisTech, 2010. Français. ⟨NNT : ⟩. ⟨pastel-00593649⟩
293 View
331 Download

Share

Gmail Facebook Twitter LinkedIn More