Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:


Event Address*:

Stockholm, Sweden

Language:

English

Event Date*
(no longer used):

July, 8-10

Organization:


Event Start Date:

16 July 2019

Event End Date:

16 July 2019

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
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)
Gerth Stølting Brodal
Created
01/23/1999 07:59:56 PM
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