245 citations · 482 across the 6 of their papers we have counts for
6 papers
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…
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
S. Fekete, S. Khuller, M. Klemmstein +2
The problem considered is the following. Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, compute a low-weight spanning tree…
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…
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…