Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Sanders, Peter
Solis-Oba, Roberto		dblp
dblp

BibTeX cite key*:

SanSol2001

Title

Title*:

How Helpers Hasten h-Relations

Journal

Journal Title*:

Journal of Algorithms
Journal's URL:


Download URL
for the article:

http://www.idealibrary.com/servlet/doi/10.1006/jagm.2001.1169
Language:

English

Publisher

Publisher's
Name:

Academic Press
Publisher's URL:

http://www.academicpress.com/www/journal/al.htm

Publisher's
Address:


ISSN:

0196-6774

Vol, No, pp, Date

Volume*:

41
Number:


Publishing Date:

2001

Pages*:

86-98
Number of
VG Pages:

25

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We study the problem of exchanging a set of messages among a group of
processors, where messages may consist of different numbers of
packets. We consider the model of half-duplex communication. Let
$\Lmax$ denote the maximum number of packets that a processor must
send and receive. If all the packets need to be delivered directly,
at least $\frac{3}{2}\Lmax$ communication steps are needed to solve
the problem in the worst case. We show that by allowing forwarding,
only $\frac{6}{5}\Lmax + \Oh{1}$ time steps are needed to exchange all
the messages, and this is optimal. Our work was motivated by the
importance of irregular message exchanges in distributed-memory
parallel computers, but it can also be viewed as an answer to an open
problem on scheduling file transfers posed by Coffmann, Garey,
Johnsson, and LaPaugh in 1985.

URL for the Abstract:


Categories,
Keywords:


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, VG Wort


BibTeX Entry:

@ARTICLE{SanSol2001,
AUTHOR = {Sanders, Peter and Solis-Oba, Roberto},
 TITLE = {How Helpers Hasten h-Relations},
 JOURNAL = {Journal of Algorithms},
 PUBLISHER = {Academic Press},
 YEAR = {2001},
 VOLUME = {41},
 PAGES = {86--98},
 ISBN = {0196-6774},
}

Entry last modified by Peter Sanders, 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)
Peter Sanders		Created
01/21/2002 16:21:10
Revision
1.
0.


Editor
Peter Sanders
Peter Sanders


Edit Date
21/01/2002 16:24:09
21/01/2002 16:21:10