3 citations · 4 across the 2 of their papers we have counts for
4 papers
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…