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 -