OPTIMAL SPEEDUP FOR BACKTRACK SEARCH ON A BUTTERFLY NETWORK

Authors
RANADE A
Citation
A. Ranade, OPTIMAL SPEEDUP FOR BACKTRACK SEARCH ON A BUTTERFLY NETWORK, Mathematical systems theory, 27(1), 1994, pp. 85-101
Citations number
8
Categorie Soggetti
System Science","Mathematics, Pure","Computer Applications & Cybernetics",Mathematics
Journal title
Mathematical systems theory → ACNP
ISSN journal
00255661
Volume
27
Issue
1
Year of publication
1994
Pages
85 - 101
Database
ISI
SICI code
0025-5661(1994)27:1<85:OSFBSO>2.0.ZU;2-#
Abstract
We present a generic algorithm for implementing backtrack search on an N processor butterfly network. For a backtrack search tree having M n odes the height h, our algorithm requires time O(M/N + h) with high pr obability. This is optimal and is obtained without making assumptions about the shape of the tree being searched.