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

DOI10.1147/rd.303.0242zbMath0636.68041OpenAlexW2043811185MaRDI QIDQ3776618

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

NP-complete problemsdepth-first searchbinary treesbacktracking with cutoff

Mathematics Subject Classification ID

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

Related Items

Network-based heuristics for constraint-satisfaction problems ⋮ A randomized parallel branch-and-bound algorithm ⋮ Phase transitions and the search problem ⋮ Modeling of uplink power control for cognitive radio networks: cooperative and noncooperative ⋮ New decision rules for exact search in \(N\)-queens ⋮ Unnamed Item ⋮ Performance of linear-space search algorithms ⋮ Performance of linear-space search algorithms