Randomized parallel algorithms for backtrack search and branch-and-bound computation

DOI10.1145/174130.174145MaRDI QIDQ3140025zbMATH OpenOpenAlexFDO

Authors Richard Karp, Yanjun Zhang

Publication date 23 June 1994

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/174130.174145

zbMATH Keywords

Backtrack searchbranch-and-bounddistributed parallel computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Distributed algorithms (68W15)

Recommendations

• A randomized parallel backtracking algorithm
• Space-Efficient Parallel Algorithms for Combinatorial Search Problems
• A randomized parallel branch-and-bound algorithm
• Branch and bound on the network model
• Efficiency of randomized parallel backtrack search

Cited in

(22)

• Efficiency of randomized parallel backtrack search
• Architecture independent parallel selection with applications to parallel priority queues
• Analysis of randomized load distribution for reproduction trees in linear arrays and rings
• Upper bounds on number of steals in rooted trees
• PARSSSE: AN ADAPTIVE PARALLEL STATE SPACE SEARCH ENGINE
• Optimal (v,5,2,1) optical orthogonal codes of small v
• A randomized parallel backtracking algorithm
• Space-efficient scheduling of stochastically generated tasks
• Efficient randomized load distribution for tree structured computations on parallel and distributed computer systems
• A review of literature on parallel constraint solving
• scientific article; zbMATH DE number 1860736 (Why is no real title available?)
• Parallel algorithms for a multi-level network optimization problem
• Deterministic branch-and-bound on distributed memory machines
• A METHOD FOR EVALUATING THE EXPECTED LOAD OF DYNAMIC TREE EMBEDDINGS IN HYPERCUBES
• The scalability analysis of a parallel tree search algorithm
• Branch and bound on the network model
• Deterministic parallel backtrack search
• Parallel best-first branch-and-bound in discrete optimization: a framework
• Asymptotically optimal dynamic tree evolution by rapidly mixing random walks on regular networks
• A simple yet exact analysis of the MultiQueue
• Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
• On the efficiency of localized work stealing

This page was built for publication: Randomized parallel algorithms for backtrack search and branch-and-bound computation

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