Informatics Report Series


Report   

EDI-INF-RR-0347


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Priority queues with binary priorities
Authors: Kyriakos Kalorkoti ; D.H. Tulley
Date: 2001
Publication Title:Theoretical Computer Science
Publisher:Elsevier
Publication Type:Journal Article Publication Status:Published
Volume No:262 Page Nos:133-144
DOI:10.1016/S0304-3975(00)00186-9
Abstract:
We consider a priority queue of unbounded capacity whose input is the sequence 1,2,...,n where each i is given a binary priority. We prove a previously conjectured recurrence for the number of allowable input-output pairs achievable by such a priority queue with z items of priority 0; the proof provides a new application of inseperable permutations. We then give upper and lower bounds for this and deduce that for fixed z the growth rate is $\Theta(n!\log^z(n))$. We also study the total number of allowable input-output pairs where the number of items of priority 0 is not fixed and provide very tight upper and lower bounds which imply that the growth rate is $\Theta(nn!\log(n))$.
Links To Paper
No links available
Bibtex format
@Article{EDI-INF-RR-0347,
author = { Kyriakos Kalorkoti and D.H. Tulley },
title = {Priority queues with binary priorities},
journal = {Theoretical Computer Science},
publisher = {Elsevier},
year = 2001,
volume = {262},
pages = {133-144},
doi = {10.1016/S0304-3975(00)00186-9},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh