3 citations · 8 across the 7 of their papers we have counts for
7 papers
Improved approximation algorithms for -connected -dominating set problems
Zeev Nutov
A graph is -connected if it has internally-disjoint paths between every pair of nodes. A subset of nodes in a graph is a -connected set if the subgraph ind…
A LP approximation for the Tree Augmentation Problem
Guy Kortsarz, Zeev Nutov
In the Tree Augmentation Problem (TAP) the goal is to augment a tree by a minimum size edge set from a given edge set such that is -edge-connected. The be…
A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
Guy Kortsarz, Zeev Nutov
The Tree Augmentation Problem (TAP) is: given a connected graph and an edge set on find a minimum size subset of edges such that $(V,{\cal…
Approximating {0,1,2}-Survivable Networks with Minimum Number of Steiner Points
Nachshon Cohen, Zeev Nutov
We consider low connectivity variants of the Survivable Network with Minimum Number of Steiner Points (SN-MSP) problem: given a finite set of terminals in a metric space (M,d),…
Approximating minimum-cost edge-covers of crossing biset-families
Zeev Nutov
An ordered pair of subsets of is called a {\em biset} if ; is the co-biset of . Two bisets intersect…
Approximating minimum-power edge-multicovers
Nachshon Cohen, Zeev Nutov
Given a graph with edge costs, the {\em power} of a node is themaximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by…