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:




Library Locked Library locked




Author, Editor

Author(s):

Elmasry, Amr

dblp



Editor(s):

Matthieu, Claire

dblp

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

URL of the conference:

http://www.siam.org/meetings/da09/

URL for downloading the paper:

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
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)
[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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
paper.pdf