Graphs where Search Methods are Indistinguishable
From MaRDI portal
Publication:6376502
arXiv2109.00035MaRDI QIDQ6376502FDOQ6376502
Authors: Matjaž Krnc, Nevena Pivač 
Publication date: 31 August 2021
Abstract: Graph searching is one of the simplest and most widely used tools in graph algorithms. Every graph search method is defined using some particular selection rule, and the analysis of the corresponding vertex orderings can aid greatly in devising algorithms, writing proofs of correctness, or recognition of various graph families. We study graphs where the sets of vertex orderings produced by two different 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).
This page was built for publication: Graphs where Search Methods are Indistinguishable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6376502)
