Informatics Report Series
|
|
|
|
|
|
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},
- }
|