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):

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 04:21:10 PM
Revision
1.
0.


Editor
Peter Sanders
Peter Sanders


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