TY - GEN
T1 - Faster kinetic heaps and their use in broadcast scheduling
AU - Kaplan, Haim
AU - Tarjan, Robert E.
AU - Tsioutsiouliklis, Kostas
PY - 2001
Y1 - 2001
N2 - We describe several implementations of the kinetic heap, a heap (priority gueue) in which the key of each item, instead of being fixed, is a linear function of time. The kinetic heap is a simple example of a kinetic data structure of the kind considered by Basch, Guibas, and Hershberger. Kinetic heaps have many applications in computational geometry, and previous implementations were designed to address these applications. We describe an additional application, to broadcast scheduling. Each of our kinetic heap implementations improves on previous implementations by being simpler or asymptotically faster for some or all applications.
AB - We describe several implementations of the kinetic heap, a heap (priority gueue) in which the key of each item, instead of being fixed, is a linear function of time. The kinetic heap is a simple example of a kinetic data structure of the kind considered by Basch, Guibas, and Hershberger. Kinetic heaps have many applications in computational geometry, and previous implementations were designed to address these applications. We describe an additional application, to broadcast scheduling. Each of our kinetic heap implementations improves on previous implementations by being simpler or asymptotically faster for some or all applications.
KW - Algorithms
KW - Theory
UR - http://www.scopus.com/inward/record.url?scp=0012640829&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0012640829&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0012640829
SN - 0898714907
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 836
EP - 844
BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
T2 - 2001 Operating Section Proceedings, American Gas Association
Y2 - 30 April 2001 through 1 May 2001
ER -