Strictly-regular number system and data structures

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Amr Ahmed Abd Elmoneim Elmasry, Claus Jensen, Jyrki Katajainen

We introduce a new number system that we call the strictly-regular system, which efficiently supports the operations: digit-increment, digit-decrement, cut, concatenate, and add. Compared to other number systems, the strictly-regular system has distinguishable properties. It is superior to the regular system for its efficient support to decrements, and superior to the extended-regular system for being more compact by using three symbols instead of four. To demonstrate the applicability of the new number system, we modify Brodal's meldable priority queues making deletion require at most 2lg n + O(1) element comparisons (improving the bound from 7lg n + O(1)) while maintaining the efficiency and the asymptotic time bounds for all operations.

OriginalsprogEngelsk
TitelAlgorithm Theory - SWAT 2010 : 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings
RedaktørerHaim Kaplan
Antal sider12
ForlagSpringer
Publikationsdato2010
Sider26-37
ISBN (Trykt)978-3-642-13730-3
ISBN (Elektronisk)978-3-642-13731-0
DOI
StatusUdgivet - 2010
Begivenhed12th Scandinavian Symposium and Workshops on Algorithm Theory - Bergen, Norge
Varighed: 21 jun. 201023 jun. 2010
Konferencens nummer: 12

Konference

Konference12th Scandinavian Symposium and Workshops on Algorithm Theory
Nummer12
LandNorge
ByBergen
Periode21/06/201023/06/2010
NavnLecture notes in computer science
Vol/bind6139
ISSN0302-9743

ID: 172855932