MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Brodal, Gerth Stølting
Pinotti, M. Cristina		dblp
dblp
Editor(s):
Arnborg, Stefan
Ivansson, Lars		dblp
dblp
BibTeX cite key*:
Brodal1998c
Title, Booktitle
Title*:
Comparator Networks for Binary Heap Construction
Booktitle*:
Proceedings of the 6th Scandinavian Workshop on Algorithm Theory (SWAT-98)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Stockholm, Sweden
Language:
English
Event Date*
(no longer used):
July, 8-10
Organization:
Event Start Date:
24 September 2023
Event End Date:
24 September 2023
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1432
Number:
Month:
July
Pages:
158-168
Year*:
1998
VG Wort Pages:
ISBN/ISSN:
3-540-64682-5
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Comparator networks for constructing binary heaps of size $n$ are
presented which have size $O(n\log\log n)$ and depth $O(\log n)$. A
lower bound of $n\log\log n-O(n)$ for the size of any heap
construction network is also proven, implying that the networks
presented are within a constant factor of optimal. We give
a tight relation between the leading constants in the size of selection
networks and in the size of heap construction networks.
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{Brodal1998c,
AUTHOR = {Brodal, Gerth Stølting and Pinotti, M. Cristina},
 EDITOR = {Arnborg, Stefan and Ivansson, Lars},
 TITLE = {Comparator Networks for Binary Heap Construction},
 BOOKTITLE = {Proceedings of the 6th Scandinavian Workshop on Algorithm Theory (SWAT-98)},
 PUBLISHER = {Springer},
 YEAR = {1998},
 VOLUME = {1432},
 PAGES = {158--168},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Stockholm, Sweden},
 MONTH = {July},
 ISBN = {3-540-64682-5},
}

Entry last modified by Evelyn Haak, 03/02/2010
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)
Gerth Stølting Brodal		Created
01/23/1999 19:59:56
Revisions
7.
6.
5.
4.
3.		Editor(s)
Evelyn Haak
Uwe Brahm
Birgit Hofmann
Uwe Brahm
Uwe Brahm		Edit Dates
01/04/99 12:22:37
01.04.99 10:23:23
01.04.99 10:02:53
29.03.99 17:09:09
29.03.99 17:06:13