596 citations · 3k across the 50 of their papers we have counts for
25 papers · 2 filters
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…
Prefix Codes: Equiprobable Words, Unequal Letter Costs
Mordecai Golin, Neal E. Young
Describes a near-linear-time algorithm for a variant of Huffman coding, in which the letters may have non-uniform lengths (as in Morse code), but with the restriction that each wor…
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…
The K-Server Dual and Loose Competitiveness for Paging
Neal E. Young
This paper has two results. The first is based on the surprising observation that the well-known ``least-recently-used'' paging algorithm and the ``balance'' algorithm for weighted…
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-…