A tie-break model for graph search

Abstract : In this paper, we consider the problem of the recognition of various kinds of orderings produced by graph searches. To this aim, we introduce a new framework, the Tie-Breaking Label Search (TBLS), in order to handle a broad variety of searches. This new model is based on partial orders de ned on the label set and it uni es the General Label Search (GLS) formalism of Krueger, Simonet and Berry (2011), and the \pattern-conditions" formalism of Corneil and Krueger (2008). It allows us to derive some general properties including new pattern-conditions (yielding memory-ecient certi cates) for many usual searches, including BFS, DFS, LBFS and LDFS. Furthermore, the new model allows easy expression of multi-sweep uses of searches that depend on previous (search) orderings of the graph's vertex set.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2016, 199, pp.89-100. 〈10.1016/j.dam.2015.06.011〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01255055
Contributeur : Michel Habib <>
Soumis le : mercredi 13 janvier 2016 - 10:35:48
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03

Identifiants

Collections

Citation

Derek G. Corneil, Jérémie Dusart, Michel Habib, Antoine Mamcarz, Fabien De Montgolfier. A tie-break model for graph search. Discrete Applied Mathematics, Elsevier, 2016, 199, pp.89-100. 〈10.1016/j.dam.2015.06.011〉. 〈hal-01255055〉

Partager

Métriques

Consultations de la notice

229