### Browsing by Author "Young, Neal"

Now showing 1 - 5 of 5

###### Results Per Page

###### Sort Options

Item Designing Multi-Commodity Flow Trees(1998-10-15) Khuller, Samir; Raghavachari, Balaji; Young, NealThe 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 considers the multi-commodity flow network-design problem: given a set of multi-commodity flow demands, find a network subject to certain constraints such that the commodities can be maximally routed. This paper focuses on the case when the network is required to be a tree. The main result is an approximation algorithm for the case when the tree is required to be of constant degree. The algorithm reduces the problem to the minimum-weight balanced-separator problem; the performance guarantee of the algorithm is within a factor of 4 of the performance guarantee of the balanced-separator procedure. If Leighton and Rao's balanced-separator procedure is used, the performance guarantee is O(\log n). This improves the O(\log^2 n) approximation factor obtained by a direct application of the balanced-separator method. (Also cross-referenced as UMIACS-TR-93-20)Item Low Degree Spanning Trees of Small Weight(1998-10-15) Khuller, Samir; Raghavachari, Balaji; Young, NealGiven n points in the plane, the degree-K spanning tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low-weight degree-K spanning trees for K>2. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree three whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of degree four whose weight is at most 1.25 times the weight of a minimum spanning tree. These results solve open problems posed by Papadimitriou and Vazirani. Moreover, if a minimum spanning tree is given as part of the input, the trees can be computed in O(n) time. The results are generalized to points in higher dimensions. It is shown that for any d [greater than or equal to] 3, an arbitrary collection of points in DimD contains a spanning tree of degree three, whose weight is at most 5/3 times the weight of a minimum spanning tree. This is the first paper that achieves factors better than two for these problems. (Also cross-referenced as UMIACS-TR-94-1)Item Maintaining Directed Reachability with Few Edges(1998-10-15) Khuller, Samir; Raghavachari, Balaji; Young, NealThe MEG (minimum equivalent graph) problem is the following: ``Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes.'' This problem is NP-hard; this paper gives an approximation algorithm achieving a performance guarantee of about 1.64 in polynomial time. The algorithm achieves a performance guarantee of 1.75 in the time required for transitive closure. The heart of the MEG problem is the minimum SCSS (strongly connected spanning subgraph) problem --- the MEG problem restricted to strongly connected digraphs. For the minimum SCSS problem, the paper gives a practical, nearly linear-time implementation achieving a performance guarantee of 1.75. The algorithm and its analysis are based on the simple idea of contracting long cycles. The analysis applies directly to 2-Exchange, a general ``local improvement'' algorithm, showing that its performance guarantee is 1.75. (Also cross-referenced as UMIACS-TR-93-87)Item A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees(1998-10-15) Fekete, Sandor P.; Khuller, Samir; Klemmstein, Monika; Raghavachari, Balaji; Young, NealGiven a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at most its specified bound is considered. In particular, modifying a given spanning tree $T$ using {\em adoptions} to meet the degree constraints is considered. A novel network-flow based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previously obtained. Equally importantly, it yields the best performance guarantee among the class of algorithms that rely solely on the topology and edge weights of the given tree. The performance guarantee is the following. If the degree constraint $d(v)$ for each $v$ is at least $2$, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times $2 - \min\{\frac{d(v)-2}{\D_T(v)-2} : \D_T(v)>2\},$ where $D_T(v)$ is the initial degree of $v$. Examples are provided in which no lighter tree meeting the degree constraint exists. Linear-time algorithms are provided with the same worst-case performance guarantee. Choosing $T$ to be a minimum spanning tree yields approximation algorithms for the general problem on geometric graphs with distances induced by various $L_p$ norms. Finally, examples of Euclidean graphs are provided in which the ratio of the lengths of an optimal Traveling Salesperson path and a minimum spanning tree can be arbitrarily close to~2. (Also cross-referenced as UMIACS-TR-95-95)Item On Strongly Connected Digraphs with Bounded Cycle Length(1998-10-15) Khuller, Samir; Raghavachari, Balaji; Young, NealThe MEG (minimum equivalent graph) problem is "Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes." We consider the complexity of this problem as a function of the maximum cycle length C in the graph. If C =2, the problem is trivial. Recently it was shown that even with the restriction C = 5, the problem is NP-hard. It was conjectured that the problem is solvable in polynomial time if C =3. In this paper we prove the conjecture, showing that the problem is equivalent to maximum bipartite matching. The strong dependence of the complexity on the cycle length is in marked contrast to the relation of complexity and cycle length in undirected graphs. Undirected graphs with bounded cycle length have bounded tree width, allowing polynomial-time algorithms for many problems that are NP-hard in general. A consequence of our result is an improved approximation algorithm for the MEG problem in general graphs. The improved algorithm has a performance guarantee of about 1.61; the best previous algorithm has a performance guarantee of about 1.64. (Also cross-referenced as UMIACS-TR-94-10)