Graph Extremities Defined by Search Algorithms

Abstract : Graph search algorithms have exploited graph extremities, such as the leaves of a tree and the simplicial vertices of a chordal graph. Recently, several well-known graph search algorithms have been collectively expressed as two generic algorithms called MLS and MLSM. In this paper, we investigate the properties of the vertex that is numbered 1 by MLS on a chordal graph and by MLSM on an arbitrary graph. We explain how this vertex is an extremity of the graph. Moreover, we show the remarkable property that the minimal separators included in the neighborhood of this vertex are totally ordered by inclusion
Type de document :
Article dans une revue
Algorithms, MDPI AG, 2010, 3 (2), pp.100-124. 〈10.3390/a3020100〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00482042
Contributeur : Genevieve Simonet <>
Soumis le : vendredi 7 mai 2010 - 18:33:36
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : jeudi 16 septembre 2010 - 13:59:51

Fichier

extremities-publi.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Anne Berry, Jean R.S. Blair, Jean-Paul Bordat, Geneviève Simonet. Graph Extremities Defined by Search Algorithms. Algorithms, MDPI AG, 2010, 3 (2), pp.100-124. 〈10.3390/a3020100〉. 〈lirmm-00482042〉

Partager

Métriques

Consultations de la notice

359

Téléchargements de fichiers

242