Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
Fast priority queues for parallel branch-and-bound
verfasst von : Peter Sanders
Erschienen in: Parallel Algorithms for Irregularly Structured Problems
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Currently used parallel best first branch-and-bound algorithms either suffer from contention at a centralized priority queue or can only approximate the best first strategy. Bottleneck free algorithms for parallel priority queues are known but they cannot be implemented very efficiently on contemporary machines.We present quite simple randomized algorithms for parallel priority queues on distributed memory machines. For branch-and-bound they are asymptotically as efficient as previously known PRAM algorithms with high probability. The simplest versions require not much more communication than the approximated branch-and-bound algorithm of Karp and Zhang.