Graph Extremities Defined by Search Algorithms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Algorithms Année : 2010

Graph Extremities Defined by Search Algorithms

Résumé

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
Fichier principal
Vignette du fichier
extremities-publi.pdf (547.18 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

lirmm-00482042 , version 1 (07-05-2010)

Identifiants

Citer

Anne Berry, Jean R.S. Blair, Jean-Paul Bordat, Geneviève Simonet. Graph Extremities Defined by Search Algorithms. Algorithms, 2010, 3 (2), pp.100-124. ⟨10.3390/a3020100⟩. ⟨lirmm-00482042⟩
310 Consultations
391 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More