Loading...
Please wait, while we are loading the content...
Similar Documents
A Fast Algorithm For Complete Subcube
| Content Provider | Semantic Scholar |
|---|---|
| Author | Hal, Recognition Burch, J. Fikret Computer, Ercal |
| Copyright Year | 1997 |
| Abstract | The complete subcube recognition problem is deened as, given a collection of available processors on an n-dimensional hypercube, locate a subcube of dimension k that consists entirely of available processors, if one exists. Despite many algorithms proposed so far on this subject, improving the time complexity of this problem remains a challenge. EEciency limits that can be reached have not been exhausted yet. This paper proposes a novel algorithm to recognize all the overlapping subcubes available on an n-dimensional hypercube whose processors are partially allocated. Given P = 2 n , as the total number of processors in the hypercube, the new algorithm runs in O(n 3 n) or O(P log 2 3 log 2 P) time which is an improvement over previously proposed strategies, such as multiple-graycode, missing combination, maximal set of subcubes, and tree collapsing. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.umr.edu/~ercal/pubs/ispan-subcube.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
