Navigation – Plan du site

Vertex partitioning of a class of digraphs

Partionnement d'une classe de graphes orientés
Louis Ferre et Bertrand Jouve

Résumés

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.

Partionnement d'une classe de graphes orientés

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.

Haut de page

Pour citer cet article

Référence électronique

Louis Ferre et Bertrand Jouve, « Vertex partitioning of a class of digraphs », Mathématiques et sciences humaines [En ligne], 158 | Été 2002, mis en ligne le 10 février 2006, consulté le 20 novembre 2017. URL : http://msh.revues.org/2857

Haut de page

Droits d’auteur

© École des hautes études en sciences sociales

Haut de page