Skip navigation
Skip navigation

Analytical Results on the BFS vs. DFS Algorithm Selection Problem: Part II: Graph Search

Everitt, Tom; Hutter, Marcus


The algorithm selection problem asks to select the best algorithm for a given problem. In the companion paper (Everitt and Hutter 2015b), expected runtime was approximated as a function of search depth and probabilistic goal distribution for tree search versions of breadth-first search (BFS) and depth-first search (DFS). Here we provide an analogous analysis of BFS and DFS graph search, deriving expected runtime as a function of graph structure and goal distribution. The applicability of the...[Show more]

CollectionsANU Research Publications
Date published: 2015
Type: Conference paper
Source: Implementing Modal Tableaux Using Sentential Decision Diagrams
DOI: 10.1007/978-3-319-26350-2_15


File Description SizeFormat Image
01_Everitt_Analytical_Results_on_the_BFS_2015.pdf361.66 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator