Ron Mosenzon

collaborators

4 papers

cs.DS2025

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs

Julia Chuzhoy, Ron Mosenzon, Ohad Trabelsi

We study the directed global minimum vertex-cut problem: given a directed vertex-weighted graph $G$ , compute a vertex-cut $(L, S, R)$ in $G$ of minimum value, which is defined to be…

cs.DS2025

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs

Ron Mosenzon

We develop new $(1 + ε)$ -approximation algorithms for finding the global minimum edge-cut in a directed edge-weighted graph, and for finding the global minimum vertex-cut in a direct…

cs.DS2025

Hardness of Approximation for Shortest Path with Vector Costs

Charlie Carlson, Yury Makarychev, Ron Mosenzon

We obtain hardness of approximation results for the $ℓ_{p}$ -Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer $p \in [2,\i…

cs.DS2022

Exact Flow Sparsification Requires Unbounded Size

Robert Krauthgamer, Ron Mosenzon

Given a large edge-capacitated network $G$ and a subset of $k$ vertices called terminals, an (exact) flow sparsifier is a small network $G^{'}$ that preserves (exactly) all multicommo…