The average complexity of depth-first search with backtracking and cutoff

DOI10.1147/RD.303.0242MaRDI QIDQ3776618zbMATH OpenOpenAlexFDO

Authors Harold S. Stone, P. Sipala

Publication date 1986

Published in IBM Journal of Research and Development (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1147/rd.303.0242

zbMATH Keywords

backtracking with cutoffbinary treesdepth-first searchNP-complete problems

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1535253
• scientific article; zbMATH DE number 1334210
• On the complexity of searching in trees: average-case minimization
• scientific article; zbMATH DE number 4080977
• scientific article; zbMATH DE number 3990867
• Average-case analysis of best-first search in two representative directed acyclic graphs
• Bounding the depth of search trees
• An average analysis of backtracking on random constraint satisfaction problems
• Average-Case Lower Bounds for Searching
• Improved approximation algorithms for the average-case tree searching problem

Cited in

(9)

• Network-based heuristics for constraint-satisfaction problems
• A randomized parallel branch-and-bound algorithm
• Phase transitions and the search problem
• scientific article; zbMATH DE number 1334602 (Why is no real title available?)
• scientific article; zbMATH DE number 1535253 (Why is no real title available?)
• Performance of linear-space search algorithms
• Performance of linear-space search algorithms
• Modeling of uplink power control for cognitive radio networks: cooperative and noncooperative
• New decision rules for exact search in \(N\)-queens

This page was built for publication: The average complexity of depth-first search with backtracking and cutoff

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3776618)