A tie-break model for graph search
| Autor: | Antoine Mamcarz, Michel Habib, Derek G. Corneil, Fabien de Montgolfier, Jérémie Dusart |
|---|---|
| Přispěvatelé: | Department of Computer Science [University of Toronto] (DCS), University of Toronto, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7) |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
FOS: Computer and information sciences
BFS Bidirectional search [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] multi-sweep algorithms 0102 computer and information sciences 02 engineering and technology DFS tie-break mechanisms 01 natural sciences Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Data Structures and Algorithms (cs.DS) [INFO]Computer Science [cs] Distributed File System Mathematics Discrete mathematics Applied Mathematics Formalism (philosophy of mathematics) 010201 computation theory & mathematics Graph (abstract data type) Graph search model 020201 artificial intelligence & image processing LBFS LDFS |
| Zdroj: | Discrete Applied Mathematics Discrete Applied Mathematics, 2016, 199, pp.89-100. ⟨10.1016/j.dam.2015.06.011⟩ Discrete Applied Mathematics, Elsevier, 2016, 199, pp.89-100. ⟨10.1016/j.dam.2015.06.011⟩ |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2015.06.011⟩ |
| Popis: | International audience; In 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect