Construction d'un ensemble d-dominant sur un graphe en utilisant un critère donné

Résumé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. Pour citer cet article : A. Delye de Clauzade de Mazieux et al., C. R. Mecanique 334 (2006).

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. To cite this article: A. Delye de Clauzade de Mazieux et al., C. R. Mecanique 334 (2006).