Shimon Kogan

activity

20172026

most citedTarget Set Selection for Conservative Populations

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

collaborators

9 papers

cs.DS2026

$O ~ (1)$ -Depth Parallel Reachability Faster than Transitive Closure

Shimon Kogan, Merav Parter

A $d$ -shortcut of a directed graph $G = (V, E)$ is a subset of edges drawn from the transitive closure $T C (G)$ whose addition reduces the graph diameter to at most $d$ . In the special…

cs.DS2026

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 $n$ -vertex digraphs $G = (V, E)$ and a subset of sources $S \subse…

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

New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the $n$ Barrier

Shimon Kogan, Merav Parter

For an $n$ -vertex digraph $G = (V, E)$ , a \emph{shortcut set} is a (small) subset of edges $H$ taken from the transitive closure of $G$ that, when added to $G$ guarantees that the dia…

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★ 3 cited

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…

math.CO2017

On the Profile of Multiplicities of Complete Subgraphs

Uriel Feige, Anne Kenyon, Shimon Kogan

Let $G$ be a $2$ -coloring of a complete graph on $n$ vertices, for sufficiently large $n$ . We prove that $G$ contains at least $n^{(\frac{1}{4} - o (1)) l o g n}$ monochromatic comple…

O~(1)-Depth Parallel Reachability Faster than Transitive Closure

Multi-Source Reachability in Near-Optimal Time

Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets

New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the n​ Barrier

Low-Congestion Shortcuts in Constant Diameter Graphs

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

New results on large induced forests in graphs

Target Set Selection for Conservative Populations

On the Profile of Multiplicities of Complete Subgraphs

$O ~ (1)$ -Depth Parallel Reachability Faster than Transitive Closure

New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the $n$ Barrier