Skip navigation
Skip navigation
The system will be down for maintenance between 8:00 and 8:15am on Wednesday 12, December 2018

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

Everitt, Tom; Hutter, Marcus

Description

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
URI: http://hdl.handle.net/1885/103801
Source: Implementing Modal Tableaux Using Sentential Decision Diagrams
DOI: 10.1007/978-3-319-26350-2_15

Download

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:  27 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator