Data Structure for a Time-Based Bandwidth Reservations Problem

Simple item page
dc.creatorBrodnik, Andrej
dc.creatorNilsson, Andreas
dc.date2003-02-06
dc.date.accessioned2026-07-07T03:19:26Z
dc.date.available2026-07-07T03:19:26Z
dc.descriptionWe discuss a problem of handling resource reservations. The resource can be reserved for some time, it can be freed or it can be queried what is the largest amount of reserved resource during a time interval. We show that the problem has a lower bound of $Ω(\log n)$ per operation on average and we give a matching upper bound algorithm. Our solution also solves a dynamic version of the related problems of a prefix sum and a partial sum.
dc.identifierhttps://arxiv.org/abs/cs/0302009
dc.identifierhttp://arxiv.org/abs/cs/0302009
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31457
dc.subjectData Structures and Algorithms
dc.subjectNetworking and Internet Architecture
dc.subjectE.1; C.2.3
dc.titleData Structure for a Time-Based Bandwidth Reservations Problem
dc.typetext

Files

Collections

arXiv