3 citations · 4 across the 2 of their papers we have counts for
5 papers · 1 filter
Optimal Distance Labeling for Permutation Graphs
Paweł Gawrychowski, Wojciech Janczewski
A permutation graph is the intersection graph of a set of segments between two parallel lines. In other words, they are defined by a permutation on elements, such that …
Conditional Lower Bounds for Variants of Dynamic LIS
Paweł Gawrychowski, Wojciech Janczewski
In this note, we consider the complexity of maintaining the longest increasing subsequence (LIS) of an array under (i) inserting an element, and (ii) deleting an element of an arra…
Fully Dynamic Approximation of LIS in Polylogarithmic Time
Paweł Gawrychowski, Wojciech Janczewski
We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under (i) inserting an element, and (ii) deleting an element of an array. In a recent bre…
Efficient Labeling for Reachability in Digraphs
Maciej Dulęba, Paweł Gawrychowski, Wojciech Janczewski
We consider labeling nodes of a directed graph for reachability queries. A reachability labeling scheme for such a graph assigns a binary string, called a label, to each node. Then…
Shorter Labels for Routing in Trees
Paweł Gawrychowski, Wojciech Janczewski, Jakub Łopuszański
A routing labeling scheme assigns a binary string, called a label, to each node in a network, and chooses a distinct port number from for every edge outgoing from…