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
Document type :
Journal articles
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00482042
Contributor : Genevieve Simonet <>
Submitted on : Friday, May 7, 2010 - 6:33:36 PM
Last modification on : Tuesday, January 28, 2020 - 11:16:04 AM
Long-term archiving on: Thursday, September 16, 2010 - 1:59:51 PM

File

extremities-publi.pdf
Publisher files allowed on an open archive

Identifiers

Citation

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

Share

Metrics

Record views

544

Files downloads

583