Comptes Rendus
no. 11
Construction d'un ensemble d-dominant sur un graphe en utilisant un critère donné

Présenté par : Jacques Arsac

Alexandre Delye de Clauzade de Mazieux1 ; Michel Marot1 ; Monique Becker1 
1 Laboratoire SAMOVAR CNRS, UMR 5157, Institut national des télécommunications – GET INT, 9, rue C. Fourier, 91011 Evry CEDEX, France
Comptes Rendus. Mécanique, Volume 334 (2006) no. 11, pp. 669-673.

Les ensembles d-dominants dans les graphes sont très importants en ingénierie des systèmes et réseaux. Leurs constructions constituent donc un thème de recherche essentiel. Nous proposons une heuristique permettant de construire de tels ensembles en utilisant un critère donné. Nous simplifions l'heuristique présentée ailleurs. Nous la généralisons, et démontrons l'exactitude de l'heuristique généralisée. Cette heuristique a pour avantage d'être distribuée et de supporter le passage à l'échelle.

d-dominating sets in graphs are very important in system and network engineering. Their constructions is thus an important research topic. An heuristic which forms such sets by using a given criterion is proposed. We simplify the heuristic presented elsewhere. We extend it and prove the correctness of the extended heuristic. This heuristic has the advantage of being distributed and scalable.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crme.2006.09.001
Mot clés : Théorie des graphes, Arbres, Sélection de caryommes, Recherche opérationnelle, Ensembles d-dominants, Heuristique
Keywords: Graph theory, Trees, Clusterhead selection, Operational researches, d-dominating set, Heuristic

Alexandre Delye de Clauzade de Mazieux 1 ; Michel Marot 1 ; Monique Becker 1

1 Laboratoire SAMOVAR CNRS, UMR 5157, Institut national des télécommunications – GET INT, 9, rue C. Fourier, 91011 Evry CEDEX, France 
@article{CRMECA_2006__334_11_669_0,
     author = {Alexandre Delye de Clauzade de Mazieux and Michel Marot and Monique Becker},
     title = {Construction d'un ensemble \protect\emph{d}-dominant sur un graphe en utilisant un crit\`ere donn\'e},
     journal = {Comptes Rendus. M\'ecanique},
     pages = {669--673},
     publisher = {Elsevier},
     volume = {334},
     number = {11},
     year = {2006},
     doi = {10.1016/j.crme.2006.09.001},
     language = {fr},
}
TY  - JOUR
AU  - Alexandre Delye de Clauzade de Mazieux
AU  - Michel Marot
AU  - Monique Becker
TI  - Construction d'un ensemble d-dominant sur un graphe en utilisant un critère donné
JO  - Comptes Rendus. Mécanique
PY  - 2006
SP  - 669
EP  - 673
VL  - 334
IS  - 11
PB  - Elsevier
DO  - 10.1016/j.crme.2006.09.001
LA  - fr
ID  - CRMECA_2006__334_11_669_0
ER  - 
%0 Journal Article
%A Alexandre Delye de Clauzade de Mazieux
%A Michel Marot
%A Monique Becker
%T Construction d'un ensemble d-dominant sur un graphe en utilisant un critère donné
%J Comptes Rendus. Mécanique
%D 2006
%P 669-673
%V 334
%N 11
%I Elsevier
%R 10.1016/j.crme.2006.09.001
%G fr
%F CRMECA_2006__334_11_669_0
Alexandre Delye de Clauzade de Mazieux; Michel Marot; Monique Becker. Construction d'un ensemble d-dominant sur un graphe en utilisant un critère donné. Comptes Rendus. Mécanique, Volume 334 (2006) no. 11, pp. 669-673. doi : 10.1016/j.crme.2006.09.001. https://comptes-rendus.academie-sciences.fr/mecanique/articles/10.1016/j.crme.2006.09.001/

[1] A.D. Amis, R. Prakash, T.H.P. Vuong, D.T. Huynh, Max–Min D-cluster formation in wireless ad hoc networks, in: Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Proceedings, 2000

[2] V. Mhatre; C. Rosenberg Design guidelines for wireless sensor networks: Communication, clustering and aggregation, Ad Hoc Networks Journal, Volume 2 (2004), pp. 45-63

Cité par Sources :

Commentaires - Politique