Graph Extremities Defined by Search Algorithms

Algorithms

Anne Berry¹  Jean R.S. Blair²  Jean-Paul Bordat³ 

[1] LIMOS, Université Blaise Pascal, Ensemble scientifique des Cézeaux, F-63177 Aubière, France;Department of EE & CS, United States Military Academy, West Point, NY 10996, USA; E-Mail:;LIRMM, 161, Rue Ada, F-34392 Montpellier, France; E-Mails:

关键词: graph search;    graph extremity;    LexBFS;    MCS;    MLS;   

DOI  :  10.3390/a3020100

来源: mdpi

【 摘 要 】

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.

【 授权许可】

CC BY   
© 2010 by the authors; licensee Molecular Diversity Preservation International, Basel, Switzerland.