10 citations · 54 across the 49 of their papers we have counts for
6 papers · 1 filter
Fully Dynamic MIS in Uniformly Sparse Graphs
Krzysztof Onak, Baruch Schieber, Shay Solomon +1
We consider the problem of maintaining a maximal independent set (MIS) in a dynamic graph subject to edge insertions and deletions. Recently, Assadi, Onak, Schieber and Solomon (ST…
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber +1
The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of…
A Generalized Matching Reconfiguration Problem
Noam Solomon, Shay Solomon
The goal in {\em reconfiguration problems} is to compute a {\em gradual transformation} between two feasible solutions of a problem such that all intermediate solutions are also fe…
Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber +1
A maximal independent set (MIS) can be maintained in an evolving -edge graph by simply recomputing it from scratch in time after each update. But can it be maintained in…
Representations of Sparse Distributed Networks: A Locality-Sensitive Approach
Haim Kaplan, Shay Solomon
In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a low outdegree orientation of a dynamic uniformly sparse graph. Specifically, for a dynamic graph on -verti…
Wireless Expanders
Shirel Attali, Merav Parter, David Peleg +1
This paper introduces an extended notion of expansion suitable for radio networks. A graph is called an -{wireless expander} if for every subset $S \subseteq…