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. \par 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.
Type de document :
Rapport
09006, 2009
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371177
Contributeur : Genevieve Simonet <>
Soumis le : jeudi 26 mars 2009 - 16:39:32
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 14:25:36

Fichier

krueger_al_GLS.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00371177, version 1

Citation

Richard Krueger, Geneviève Simonet, Anne Berry. A General Label Search to Investigate Classical Graph Search Algorithms. 09006, 2009. 〈lirmm-00371177〉

Partager

Métriques

Consultations de la notice

187

Téléchargements de fichiers

411