Technical, Research Report
@TechReport
Technischer-, Forschungsbericht


Show entries of:

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

Action:

login to update

Options:









Author, Editor

Author(s):

Elmasry, Amr

dblp



Editor(s):

Elmasry, Amr

dblp



BibTeX Citekey*:

Elmasry2008d

Language:

English

Title, Institution

Title*:

Violation Heaps: A Better Substitute for Fibonacci Heaps

Institution*:

CoRR

Publishers or Institutions Address*:

http://arxiv.org/abs/0812.2851

Type:

Research Report

No, Year, pp.,

Number*:

CoRR abs/0812.2851

Pages*:

10

Month:


VG Wort
Pages*:

1-10

Year*:

2008

ISBN/ISSN:






DOI:




Note, Abstract, ©

Note:


(LaTeX) Abstract:

We give a priority queue that achieves the same amortized bounds as Fibonacci heaps. Namely, find-min requires $O(1)$ worst-case time, insert, meld and decrease-key require $O(1)$ amortized time, and delete-min requires $O(\log n)$ amortized time. Our structure is simple and promises a more efficient practical behavior compared to any other known Fibonacci-like heap.

Categories / Keywords:

Data Structures, Fibonacci Heaps, Decrease-Key Operation

Copyright Message:


HyperLinks / References / URLs:

http://arxiv.org/abs/0812.2851

Personal Comments:


File Upload:


Download
Access Level:

Public

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, VG Wort


BibTeX Entry:
@TECHREPORT{Elmasry2008d,
AUTHOR = {Elmasry, Amr},
EDITOR = {Elmasry, Amr},
TITLE = {Violation Heaps: A Better Substitute for Fibonacci Heaps},
YEAR = {2008},
TYPE = {Research Report},
INSTITUTION = {CoRR},
NUMBER = {CoRR abs/0812.2851},
PAGES = {10},
ADDRESS = {http://arxiv.org/abs/0812.2851},
}


Entry last modified by Amr Elmasry, 03/17/2009
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)
Amr Elmassry
Created
02/17/2009 08:52:00 PM
Revision
1.
0.


Editor
Amr Elmasry
Amr Elmassry


Edit Date
03/17/2009 04:38:33 PM
02/17/2009 08:52:00 PM


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
paper.pdf