Open AccessGraphs where Search Methods are Indistinguishable
Author(s) -
Matjaž Krnc,
Nevena Pivač
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.18690/978-961-286-516-0.3
Subject(s) - lexicographical order , correctness , computer science , depth first search , vertex (graph theory) , graph , bidirectional search , combinatorics , breadth first search , mathematical proof , theoretical computer science , mathematics , search algorithm , algorithm , beam search , best first search , geometry
Graph searching is one of the simplest and most widely used tools in graph algorithms. Every graph search method is defined using some partic-ular selection rule, and the analysis of the corre-sponding vertex orderings can aid greatly in de-vising algorithms, writing proofs of correctness, or recognition of various graph families. We study graphs where the sets of vertex order-ings produced by two di˙erent search methods coincide. We characterise such graph families for ten pairs from the best-known set of graph searches: Breadth First Search (BFS), Depth First Search (DFS), Lexicographic Breadth First Search (LexBFS) and Lexicographic Depth First Search (LexDFS), and Maximal Neighborhood Search (MNS).