10 citations · 14 across the 3 of their papers we have counts for
5 papers · 1 filter
Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling
Adrian Kosowski, Przemysław Uznański, Laurent Viennot
A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded sole…
Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond
Siddharth Gupta, Adrian Kosowski, Laurent Viennot
For fixed , we consider the task of adding to a graph a set of weighted shortcut edges on the same vertex set, such that the length of a shortest -hop path between…
Universal Protocols for Information Dissemination Using Emergent Signals
Bartlomiej Dudek, Adrian Kosowski
We consider a population of agents which communicate with each other in a decentralized manner, through random pairwise interactions. One or more agents in the population may a…
Approximation Strategies for Generalized Binary Search in Weighted Trees
Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznanski +1
We consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node in a given tree . Upon querying a node…
On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols
Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski +3
In this work we focus on a natural class of population protocols whose dynamics are modelled by the discrete version of Lotka-Volterra equations. In such protocols, when an agent $…