Shimon Kogan

activity

20192022

most citedLow-Congestion Shortcuts in Constant Diameter Graphs

3 citations · 5 across the 3 of their papers we have counts for

collaborators

5 papers

cs.DS2022★ 1 cited

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…

cs.DS2021★ 3 cited

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…

math.CO2020

A note on a Caro-Wei bound for the bipartite independence number in graphs

Shimon Kogan

A bi-hole of size $t$ in a bipartite graph $G$ is a copy of $K_{t, t}$ in the bipartite complement of $G$ . Given an $n \times n$ bipartite graph $G$ , let $β (G)$ be the largest $k$ f…

math.CO2019★ 1 cited

New results on large induced forests in graphs

Shimon Kogan

For a graph $G$ , let $a (G)$ denote the maximum size of a subset of vertices that induces a forest. We prove the following. 1. Let $G$ be a graph of order $n$ , maximum degree $Δ > 0$ …

cs.DS2019

Target Set Selection for Conservative Populations

Uriel Feige, Shimon Kogan

Let $G = (V, E)$ be a graph on $n$ vertices, where $d_{v}$ denotes the degree of vertex $v$ , and $t_{v}$ is a threshold associated with $v$ . We consider a process in which initially a s…