11 citations · 17 across the 11 of their papers we have counts for
8 papers · 1 filter
Online Bin Covering with Exact Parameter Advice
Andrej Brodnik, Bengt J. Nilsson, Gordana Vujovic
We show an asymptotic 2/3-competitive strategy for the bin covering problem using O(b+log n) bits of advice, where b is the number of bits used to encode a rational value and n is…
A subquadratic algorithm for the simultaneous conjugacy problem
Andrej Brodnik, Aleksander Malnič, Rok Požar
The -Simultaneous Conjugacy problem in the symmetric group asks whether there exists a permutation such that holds for all $j = 1,2,\ldots,…
Sliding Suffix Tree using LCA
Andrej Brodnik, Matevž Jekovec
We consider a sliding window over a stream of characters from some alphabet of constant size. The user wants to perform deterministic substring matching on the current sliding…
Parallel Query in the Suffix Tree
Matevž Jekovec, Andrej Brodnik
Given the query string of length , we explore a parallel query in a static suffix tree based data structure for , where is the number of processors and is the l…
Speeding up shortest path algorithms
Andrej Brodnik, Marko Grgurovič
Given an arbitrary, non-negatively weighted, directed graph we present an algorithm that computes all pairs shortest paths in time $\mathcal{O}(m^* n + m \lg n + nT_ψ(m^*…
An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture
Andrej Brodnik, Johan Karlsson, J. Ian Munro +1
In this paper we study the Prefix Sum problem introduced by Fredman. We show that it is possible to perform both update and retrieval in O(1) time simultaneously under a memory mod…
Static Data Structure for Discrete Advance Bandwidth Reservations on the Internet
Andrej Brodnik, Andreas Nilsson
In this paper we present a discrete data structure for reservations of limited resources. A reservation is defined as a tuple consisting of the time interval of when the resource s…
Data Structure for a Time-Based Bandwidth Reservations Problem
Andrej Brodnik, Andreas Nilsson
We 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 reso…