3 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 , compute a vertex-cut in 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 -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 direc…
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 -Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer $p \in [2,\i…