Skip to Main content Skip to Navigation
Journal articles

A General Label Search to Investigate Classical Graph Search Algorithms

Abstract : Many graph search algorithms use a labeling of the vertices to compute an ordering of the vertices. We generalize this idea by devising a general vertex labeling algorithmic process called General Label Search (GLS), which uses a labeling structure which, when specified, defines specific algorithms. We characterize the vertex orderings computable by the basic types of searches in terms of properties of their associated labeling structures. We then consider performing graph searches in the complement without computing it, and provide characterizations for some searches, but show that for some searches such as the basic Depth-First Search, no algorithm of the GLS family can exactly find all the orderings of the complement. Finally, we present some implementations and complexity results of GLS on a graph and on its complement.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00565874
Contributor : Genevieve Simonet Connect in order to contact the contributor
Submitted on : Monday, February 14, 2011 - 7:05:48 PM
Last modification on : Wednesday, February 24, 2021 - 4:24:01 PM

File

publiGLS.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Geneviève Simonet, Anne Berry, Richard Krueger. A General Label Search to Investigate Classical Graph Search Algorithms. Discrete Applied Mathematics, Elsevier, 2011, 159, pp.128-142. ⟨10.1016/j.dam.2010.02.011⟩. ⟨lirmm-00565874⟩

Share

Metrics

Record views

577

Files downloads

590