Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Maggs, Bruce M.
Vöcking, Berthold

dblp
dblp



BibTeX cite key*:

Vocking2000

Title

Title*:

Improved Routing and Sorting on Multibutterflies

Journal

Journal Title*:

Algorithmica

Journal's URL:

http://link.springer-ny.com/link/service/journals/00453/

Download URL
for the article:

http://link.springer.de/link/service/journals/00453/contents/00/10049/paper/10049.pdf

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer-ny.com/

Publisher's
Address:

New York, USA

ISSN:

0178-4617

Vol, No, pp, Date

Volume*:

28

Number:

4

Publishing Date:

December 2000

Pages*:

438-464

Number of
VG Pages:

30

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

This paper shows that an $N$-node AKS network (as described by Paterson) can be embedded in a
$\frac{3N}{2}$-node degree-8 multibutterfly network with load 1, congestion 1, and dilation 2. The result
has several implications, including the first deterministic algorithms for sorting and finding the median of $n
\log n$ keys on an $n$-input multibutterfly in $O(\log n)$ time, a work-efficient deterministic algorithm for
finding the median of $n \log^2 n \log\log n$ keys on an $n$-input multibutterfly in $O(\log n \log\log n)$
time, and a three-dimensional VLSI layout for the $n$-input AKS network with volume $O(n^{3/2})$.
While these algorithms are not practical, they provide further evidence of the robustness of multibutterfly
networks. We also present a separate, and more practical, deterministic algorithm for routing $h$ relations on
an $n$-input multibutterfly in $O(h + \log n)$ time. Previously, only algorithms for solving $h$ one-to-one
routing problems were known. Finally, we show that a 2-folded butterfly, whose individual splitters do not
exhibit expansion, can emulate a bounded-degree multibutterfly with $(\alpha,\beta)$-expansion, for any
$\alpha \cdot \beta < 1/4$.

URL for the Abstract:

http://www.mpi-sb.mpg.de/~voecking/abstracts/MBF.html

Categories,
Keywords:

Networks, Sorting, Routing

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:

@ARTICLE{Vocking2000,
AUTHOR = {Maggs, Bruce M. and V{\"o}cking, Berthold},
TITLE = {Improved Routing and Sorting on Multibutterflies},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2000},
NUMBER = {4},
VOLUME = {28},
PAGES = {438--464},
ADDRESS = {New York, USA},
MONTH = {December},
ISBN = {0178-4617},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Berthold Voecking
Created
02/27/2001 05:08:26 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Uwe Brahm
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker
Edit Dates
05/02/2001 11:29:39 AM
05/02/2001 11:28:46 AM
20.03.2001 17:15:27
09.03.2001 14:37:20
05.03.2001 10:26:13