245 citations · 596 across the 23 of their papers we have counts for
6 papers · 1 filter
Designing Multi-Commodity Flow Trees
Samir Khuller, Balaji Raghavachari, Neal E. Young
The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands. This paper consider…
Balancing Minimum Spanning and Shortest Path Trees
Samir Khuller, Balaji Raghavachari, Neal E. Young
This paper give a simple linear-time algorithm that, given a weighted digraph, finds a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tr…
Low-Degree Spanning Trees of Small Weight
Samir Khuller, Balaji Raghavachari, Neal E. Young
The degree-d spanning tree problem asks for a minimum-weight spanning tree in which the degree of each vertex is at most d. When d=2 the problem is TSP, and in this case, the well-…
Approximating the Minimum Equivalent Digraph
Samir Khuller, Balaji Raghavachari, Neal E. Young
The MEG (minimum equivalent graph) problem is, given a directed graph, to find a small subset of the edges that maintains all reachability relations between nodes. The problem is N…
A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover
Samir Khuller, Uzi Vishkin, Neal Young
The paper describes a simple deterministic parallel/distributed (2+epsilon)-approximation algorithm for the minimum-weight vertex-cover problem and its dual (edge/element packing).
On Strongly Connected Digraphs with Bounded Cycle Length
Samir Khuller, Balaji Raghavachari, Neal Young
The MEG (minimum equivalent graph) problem is, given a directed graph, to find a small subset of the edges that maintains all reachability relations between nodes. The problem is N…