Divide-and-conquer algorithms on the hypercube

Ernst W. Mayr, Ralph Werchner

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

1 Zitat (Scopus)

Abstract

We show how to implement divide-and-conquer algorithms with* out undue overhead on a wide class of networks. We give an optimal generic divide-and-conquer implementation on hypercubes for the class of divide-and-conquer algorithms for which the total size of the subproblems on any level of the recursion does not exceed the parent problem size. For this implementation, appropriately sized subcubes have to be allocated to the subproblems generated by the divide-steps. We take care that these allocation steps do not cause any unbalanced distribution of work, and that, asymptotically, they do not increase the running time. Variants of our generic algorithm also work for the butterfly network and, by a general simulation, for the class of hypercu-bic networks, including the shuffle-exchange and the cube-connected-cycles network. Our results can also be applied to optimally solve various types of routing problems.

OriginalspracheEnglisch
TitelSTACS 1993 - 10th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Redakteure/-innenPatrice Enjalbert, Alain Finkel, Klaus W. Wagner
Herausgeber (Verlag)Springer Verlag
Seiten153-162
Seitenumfang10
ISBN (Print)9783540565031
DOIs
PublikationsstatusVeröffentlicht - 1993
Extern publiziertJa
Veranstaltung10th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1993 - Wurzburg, Deutschland
Dauer: 25 Feb. 199327 Feb. 1993

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band665 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Konferenz

Konferenz10th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1993
Land/GebietDeutschland
OrtWurzburg
Zeitraum25/02/9327/02/93

Fingerprint

Untersuchen Sie die Forschungsthemen von „Divide-and-conquer algorithms on the hypercube“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren