10 citations · 54 across the 49 of their papers we have counts for
64 papers
Dynamic Edge Orientation via Random Walks: From Trees to Outerplanar Graphs and Beyond
Gabriel Marques Domingues, Minh Hang Nguyen, Shay Solomon
We study the \emph{fully dynamic edge orientation problem}, focusing on \emph{worst-case} time bounds. An undirected graph undergoes edge insertions and deletions, and the goal is…
Improved Euclidean Shallow Light Trees
Hung Le, Shay Solomon, Cuong Than +2
For parameters , a spanning tree of a weighted graph rooted at a designated vertex is called an -shallow-light tree (SLT) if (i) for every vertex ,…
Dynamic Dominating Set in Uniformly Sparse Graphs
Anton Bukov, Shay Solomon
In the dynamic {\em minimum dominating set (MDS)} problem, the goal is to efficiently maintain an approximate MDS in an -vertex graph with vertex costs in undergoing e…
Approximating Euclidean Shallow-Light Trees
Hung Le, Shay Solomon, Cuong Than +2
For a weighted graph and a designated source vertex , a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source and a minimum…
Dynamic Set Cover with Worst-Case Recourse
Shay Solomon, Amitai Uzrad
In the dynamic set cover (SC) problem, the input is a dynamic universe of at most elements and a fixed collection of sets, where each element belongs to at most sets an…
Vizing's Theorem in Deterministic Almost-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3
Vizing's theorem states that any -vertex -edge graph of maximum degree can be edge colored using at most different colors. Vizing's original proof is easily transl…