MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Elmasry, Amrdblp
Editor(s):
Matthieu, Clairedblp
Not MPII Editor(s):
Matthieu, Claire
BibTeX cite key*:
Elmasry2009
Title, Booktitle
Title*:
Pairing Heaps with O(log log n) decrease Cost
paper.pdf (115.63 KB)
Booktitle*:
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da09/
Downloading URL:
http://www.siam.org/proceedings/soda/2009/SODA09_052_elmasrya.pdf
Event Address*:
New York, USA
Language:
English
Event Date*
(no longer used):
Organization:
Association for Computing Machinery (ACM) and Society for Industrial and Applied Mathematics (SIAM)
Event Start Date:
4 January 2009
Event End Date:
6 January 2009
Publisher
Name*:
ACM
URL:
http://www.siam.org/
Address*:
New York, NY
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
471-476
Year*:
2009
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We give a variation of the pairing heaps for which the time bounds for all the operations match the lower bound proved by Fredman for a family of similar self-adjusting heaps.
Namely, our heap structure requires $O(1)$ for insert and find-min, $O(\log{n})$ for delete-min, and $O(\log\log{n})$ for decrease-key and meld (all the bounds are in the amortized sense except for find-min).
Keywords:
Algorithms, Data structures, Self-Adjusting Structures, Pairing Heaps, Amortized Analysis
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Elmasry2009,
AUTHOR = {Elmasry, Amr},
EDITOR = {Matthieu, Claire},
TITLE = {Pairing Heaps with {O(log} log n) decrease Cost},
BOOKTITLE = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)},
PUBLISHER = {ACM},
YEAR = {2009},
ORGANIZATION = {Association for Computing Machinery (ACM) and Society for Industrial and Applied Mathematics (SIAM)},
PAGES = {471--476},
ADDRESS = {New York, USA},
MONTH = {January},
}


Entry last modified by Anja Becker, 03/05/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)
[Library]
Created
02/17/2009 06:48:58 PM
Revisions
10.
9.
8.
7.
6.
Editor(s)
Anja Becker
Anja Becker
Anja Becker
Amr Elmasry
Amr Elmasry
Edit Dates
05.03.2010 09:23:19
05.03.2010 09:22:42
05.03.2010 09:18:52
04/07/2009 05:02:09 PM
04/07/2009 04:59:41 PM


File Attachment Icon
paper.pdf