A tie-break model for graph search

International audienceIn this paper, we consider the problem of the recognition of various kinds of orderings produced bygraph 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 denedon the label set and it unies the General Label Search (GLS) formalism of Krueger, Simonet andBerry (2011), and the \pattern-conditions" formalism of Corneil and Krueger (2008). It allowsus to derive some general properties including new pattern-conditions (yielding memory-ecientcerticates) for many usual searches, including BFS, DFS, LBFS and LDFS. Furthermore, thenew model allows easy expression of multi-sweep uses of searches that depend on previous (search)orderings of the graph's vertex set