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

Sibeyn, Jop F.

dblp



BibTeX cite key*:

F.Sibeyn-SIAM-1999

Title

Title*:

Row-Major Sorting on Meshes

Journal

Journal Title*:

SIAM Journal on Computing

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

SIAM

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

28

Number:

3

Publishing Date:

June 1999

Pages*:

847-863

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

In all recent near-optimal sorting algorithms for meshes, the
packets are sorted with respect to some snake-like indexing. In
this paper we present deterministic algorithms for sorting with
respect to the more natural row-major indexing.

For 1-1 sorting on an $n \times n$ mesh, we give an algorithm that
runs in $2 \cdot n + o(n)$ steps, matching the distance bound, with
maximal queue size five. It is considerably simpler than earlier
algorithms. Another algorithm performs $k$-$k$ sorting in $k \cdot
n / 2 + o(k \cdot n)$ steps, matching the bisection bound.

Furthermore, we present {\em uni-axial} algorithms for row-major
sorting. We show that 1-1 sorting can
be performed in $2\breukk{1}{2} \cdot n + o(n)$ steps.
Alternatively, this problem is solved with maximal queue size five
in $4\breukk{1}{3} \cdot n$ steps, without any additional terms.

URL for the Abstract:


Categories,
Keywords:

Algorithms, Meshes, Routing, Sorting, Row-Major

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

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


BibTeX Entry:

@ARTICLE{F.Sibeyn-SIAM-1999,
AUTHOR = {Sibeyn, Jop F.},
TITLE = {Row-Major Sorting on Meshes},
JOURNAL = {SIAM Journal on Computing},
PUBLISHER = {SIAM},
YEAR = {1999},
NUMBER = {3},
VOLUME = {28},
PAGES = {847--863},
MONTH = {June},
}


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)
Jop F. Sibeyn
Created
02/19/2000 03:52:35 PM
Revisions
2.
1.
0.

Editor(s)
Uwe Brahm
Anja Becker
Jop F. Sibeyn

Edit Dates
02/14/2005 08:07:39 PM
29.03.2000 15:45:34
19/02/2000 15:52:35

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section