| Titre | Vertex partitioning of a class of digraphs | |
|---|---|---|
| Auteur | Louis Ferre, Bertrand Jouve | |
 |
Revue | Mathématiques et sciences humaines |
| Numéro | no 158, été 2002 | |
| 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. Source : Éditeur (via OpenEdition Journals) |
|
| Résumé anglais |
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. Source : Éditeur (via OpenEdition Journals) |
|
| Article en ligne | http://msh.revues.org/2857 |
