Mathématiques et sciences humaines/Mathematics and social sciences

n° 158, Été 2002

Version imprimable   Signaler cette page  

Vertex partitioning of a class of digraphs

Partionnement d'une classe de graphes orientés

Louis Ferre et Bertrand Jouve

Résumé

Un ensemble de sommets V' d'un graphe orienté G = (V,A) est un pseudo puits si son demi-degré extérieur est faible. La recherche d'un pseudo puits dans un graphe d'ordre élevé est un problème de forte complexité combinatoire. Nous montrons, sur une famille partitulière de graphes, que l'utilisation d'une classification hiérarchique des sommets, dont l'ensemble est muni d'une métrique bien choisie, permet la mise en évidence de pseudo puits par leur agrégation en 1er.

Abstract

A vertex subset V' of a digraph is a pseudo sink set if its out-degree is low. The research of a pseudo sink set in a digraph is a high complexity combinatory problem. We show, for a particular family of digraphs, that a clustering of the vertex set fitted with a well chosen metric allows to reveal pseudo sink sets by their aggregation in a first level.

Index

Pour citer cet article

Louis Ferre et Bertrand Jouve, « Vertex partitioning of a class of digraphs », Mathématiques et sciences humaines, n° 158, Été 2002, [En ligne], mis en ligne le 10 février 2006. URL : http://msh.revues.org/document2857.html. Consulté le 28 novembre 2009.

 
Page générée par Lodel - Nous adhérons à www.revues.org

ISSN : 0987 6936
Ecole des hautes études en sciences sociales