Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2020) |
last year
(2019) |
two years ago
(2018) |
Notes URL
Action:
login to update
Options:
Goto entry point
Author, Editor
Author(s):
Chong, Ka Wong
Ramos, Edgar A.
dblp
dblp
Editor(s):
Bilardi, Gianfranco
Italiano, Giuseppe F.
Pietracaprina, Andrea
Pucci, Geppino
dblp
dblp
dblp
dblp
BibTeX cite key*:
Chong-Ramos1998
Title, Booktitle
Title*:
Improved deterministic parallel padded sorting
Booktitle*:
Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98)
Event, URLs
URL of the conference:
URL for downloading the paper:
Event Address*:
Venice, Italy
Language:
English
Event Date*
(no longer used):
August 24-26
Organization:
Event Start Date:
14 August 2020
Event End Date:
14 August 2020
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1461
Number:
Month:
Pages:
405-416
Year*:
1998
VG Wort Pages:
ISBN/ISSN:
3-540-64848-8
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Given an input array of $n$ real numbers, sorting with padding
$\lambda$ consists in writing those numbers in order in an array of
size $(1+\lambda)n$, thus leaving $\lambda n$ entries {\em empty}.
Only comparisons are allowed between the numbers to be sorted. We
describe an algorithm that, with $nk$ processors in the CRCW PRAM
model, sorts the input array with padding $o(1)$ using time
$
O(\log_k n \log^*(\log_k n)+\loglog k)
$.
This improves a previous algorithm %by Hagerup and Raman %\cite{HaRa93}
with time bound %(after an improvement in \cite{GoZw95})
$
O(\log_k n $ $(\loglog k)^3\cdot 2^{C(\log^* n-\log^*k)})
$.
The best known lower bound is $\Omega(\log_k n)$.
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:
@INPROCEEDINGS
{
Chong-Ramos1998
,
AUTHOR = {Chong, Ka Wong and Ramos, Edgar A.},
EDITOR = {Bilardi, Gianfranco and Italiano, Giuseppe F. and Pietracaprina, Andrea and Pucci, Geppino},
TITLE = {Improved deterministic parallel padded sorting},
BOOKTITLE = {Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98)},
PUBLISHER = {Springer},
YEAR = {1998},
VOLUME = {1461},
PAGES = {405--416},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Venice, Italy},
ISBN = {3-540-64848-8},
}
Entry last modified by Evelyn Haak, 03/02/2010
Edit History (please click the blue arrow to see the details)
Edit History (please click the blue arrow to see the details)
Editor(s)
Edgar A. Ramos
Created
02/12/1999 08:20:59 PM
Revisions
3.
2.
1.
0.
Editor(s)
Evelyn Haak
Uwe Brahm
Uwe Brahm
Edgar A. Ramos
Edit Dates
01/04/99 12:28:04
29.03.99 18:33:00
29.03.99 18:31:29
12/02/99 20:20:59