Abstract | ||
---|---|---|
The parallel complexity of a search strategy that combines attributes of both breadth-firstsearch and depth-first search is studied. The search called breadth-depth search was definedby Horowitz and Sahni. The search technique has applications in branch-and-bound strategies.Kindervater and Lenstra posed the complexity of this type of search strategy as an openproblem. We resolve their question by showing that a natural decision problem based onbreadth-depth search is P-complete.... |
Year | Venue | Keywords |
---|---|---|
1993 | Parallel Processing Letters | branch and bound,decision problem,depth first search |
Field | DocType | Volume |
Incremental heuristic search,Combinatorics,Mathematical optimization,Search algorithm,Computer science,Parallel computing,Depth-first search,Beam stack search,Beam search,Jump search,Best-first search,Iterative deepening depth-first search | Journal | 3 |
Citations | PageRank | References |
5 | 0.53 | 3 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Raymond Greenlaw | 1 | 142 | 18.56 |