Technical, Research Report
@TechReport
Technischer-, Forschungsbericht


Show entries of:

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

Action:

login to update

Options:









Author, Editor
Author(s):
Elmasry, Amrdblp
Editor(s):
Elmasry, Amrdblp

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


File Attachment Icon
paper.pdf