Browsing Institutt for datateknologi og informatikk by Subject "VDP::Algorithms and computability theory: 422"
Now showing items 1-4 of 4
-
Approximate query processing over static sets and sliding windows
(Journal article; Peer reviewed, 2021)Indexing of static and dynamic sets is fundamental to a large set of applications such as information retrieval and caching. Denoting the characteristic vector of the set by B, we consider the problem of encoding sets and ... -
Fair allocation of conflicting items
(Peer reviewed; Journal article, 2021)We study fair allocation of indivisible items, where the items are furnished with a set of conflicts, and agents are not permitted to receive conflicting items. This kind of constraint captures, for example, participating ... -
Frameworks for designing in-place graph algorithms
(Peer reviewed; Journal article, 2022)Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. More recently, several graph algorithms have been studied under ROM model. In this paper, we study graph algorithms ... -
Succinct Encodings for Families of Interval Graphs
(Journal article; Peer reviewed, 2021)We consider the problem of designing succinct data structures for interval graphs with n vertices while supporting degree, adjacency, neighborhood and shortest path queries in optimal time. Towards showing succinctness, ...