6 papers
On -connectivity oracles in -connected graphs
Zeev Nutov
A -connectivity oracle for a graph is a data structure that given determines whether there are at least internally disjoint -paths in . For un…
Approximation and parameterized algorithms for covering disjointness-compliable set families
Zeev Nutov, Anael Vaknin
A set-family is disjointness-compliable if implies or ; if is also symmetric then…
A tight example for approximation ratio 5 for covering small cuts by the primal-dual method
Zeev Nutov
In the Small Cuts Cover problem we seek to cover by a min-cost edge-set the set family of cuts of size/capacity of a graph. Recently, Simmons showed that the primal-dual algor…
Improved bicriteria approximation for -edge-connectivity
Zeev Nutov
In the -Edge Connected Spanning Subgraph (-ECSS) problem we are given a (multi-)graph with edge costs and an integer , and seek a min-cost -edge-connected spa…
Bicriteria approximation for -edge-connectivity
Zeev Nutov, Reut Cohen
In the -Edge Connected Spanning Subgraph (-ECSS) problem we are given a (multi-)graph with edge costs and an integer , and seek a min-cost -edge-connected spa…
Tight analysis of the primal-dual method for edge-covering pliable set families
Zeev Nutov
A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993: 708-717] states that the problem of covering an uncrossable set family by a min-cost edge set admits appro…