3 citations · 8 across the 9 of their papers we have counts for
6 papers · 1 filter
-Depth Parallel Reachability Faster than Transitive Closure
Shimon Kogan, Merav Parter
A -shortcut of a directed graph is a subset of edges drawn from the transitive closure whose addition reduces the graph diameter to at most . In the special…
Multi-Source Reachability in Near-Optimal Time
Shimon Kogan, Merav Parter
The multi-source reachability problem asks to compute the reachable sets from a given subset of source vertices. For -vertex digraphs and a subset of sources $S \subse…
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
Shimon Kogan, Merav Parter
Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph…
New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the Barrier
Shimon Kogan, Merav Parter
For an -vertex digraph , a \emph{shortcut set} is a (small) subset of edges taken from the transitive closure of that, when added to guarantees that the dia…
Low-Congestion Shortcuts in Constant Diameter Graphs
Shimon Kogan, Merav Parter
Low congestion shortcuts, introduced by Ghaffari and Haeupler (SODA 2016), provide a unified framework for global optimization problems in the congest model of distributed computin…
Target Set Selection for Conservative Populations
Uriel Feige, Shimon Kogan
Let be a graph on vertices, where denotes the degree of vertex , and is a threshold associated with . We consider a process in which initially a s…