Balaji Raghavachari

Dual-Homing Protection in IP-Over-WDM Networks (2008)

Designing multi-commodity flow trees

Jianping Wang, Vinod M. Vokkarane, Raja Jothi, Xiangtong Qi, Balaji Raghavachari, Jason P. Jue, ...

Abstract—A fault-tolerant scheme, called dual homing, is generally used in IP-based access networks to increase the availability of the networks. In a dual-homing architecture, a host is connected...

DOMINE: a database of protein domain interactions (2008)

Raghavachari, Balaji, Tasneem, Asba, Przytycka, Teresa M., Jothi, Raja

DOMINE is a database of known and predicted protein domain interactions compiled from a variety of sources. The database contains domain–domain interactions observed in PDB entries, and those that...

A network-flow technique for finding low-weight bounded-degree trees (2007)

Sandor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young

Given 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...

y (2007)

Dynamic Dual-Homing Protection in WDM Mesh Networks (2007)

Given n points in the Euclidean plane, the degree--MST problem asks for a spanning tree of minimum weight in which the degree of each node is at most. It is shown in this paper that, for any set of...

Vinod M. Vokkarane, Jianping Wang, Xiangtong Qi, Raja Jothi, Balaji Raghavachari, Jason P. Jue

Abstract—A fault-tolerant scheme, called dual homing, is generally used in IP-based access networks to increase the survivability of the network. However, dual homing itself cannot provide...

r (2007)

Raja Jothi, Balaji Raghavachari, V Demand V

Given an undirected graph G = (V, E) with non-negative costs on its edges, a root node

y (2007)

Balaji Raghavachari, Jeyakesavan Veerasamy

The windy postman problem is a generalization of the Chinese postman problem in which the edge-traversal costs are asymmetric. The problem is to compute a shortest tour that traverses every edge of a...

AND (2007)

Abstract. Given 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...

in the graph. If (2007)

The 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...

AND (2007)

Localization in Graphs (2007)

Abstract. The 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...

Samir Khuller, Balaji Raghavachari, Azriel Rosenfeld

Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a "graph space". The...

z (2007)

From WADS-93. Copyright Springer-Verlag. Full version: IPL 50:49-55. Designing Multi-Commodity Flow Trees (2007)

We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous trade-off: given the two...

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 considers the...

Abstract Load-balanced agent activation for value-added network services (2005)

Abstract. Given 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...

Chao Gong, Kamil Sarac, Ovidiu Daescu, Balaji Raghavachari, Raja Jothi

In relation to its growth in size and user population, the Internet faces new challenges that have triggered the proposals of value-added network services, e.g., IP multicast, IP traceback, DiffServ,...

Finding k-connected subgraphs with minimum average weight (2004)

Prabhakar Gubbala, Balaji Raghavachari

Abstract. We consider the problems of finding k-connected spanning subgraphs with minimum average weight. We show that the problems are NP-hard for k>1. Approximation algorithms are given for four...

Improved approximation algorithms for the single-sink buy-at-bulk network design problems (2004)

Survivable network design: The capacitated minimum spanning network problem (2004)

Abstract. Consider a given undirected graph G = (V; E) with nonnegative edge costs, a root node r 2 V, and a set D V of demands with dv representing the units of ow that demand v 2 D wishes to send...

Minimum latency tours and the k-traveling repairmen problem (2004)

We are given an undirected graph G = (V; E) with positive weights on its vertices representing demands, and non-negative costs on its edges. Also given are a capacity constraint k, and root vertex r...

Dynamic capacitated minimum spanning trees (2004)

Given an undirected graph G = (V; E) and a source vertex s 2 V, the k-traveling repairman (KTR) problem, also known as the minimum latency problem, asks for k tours, each starting at s and covering...

Revisiting Esau-Williams' Algorithm: On the Design of Local Access Networks (2004)

Abstract--- Given a set of terminals, each associated with a positive number denoting the traffic to be routed to a central terminal (root), the Capacitated Minimum Spanning Tree (CMST) problem asks...

Raja Jothi And, Raja Jothi, Balaji Raghavachari

Given a set of nodes, each associated with a positive number denoting the trac to be routed to a central node (root), the capacitated minimum spanning tree (CMST) problem asks for a minimum spanning...

Dynamic Dual-Homing Protection in WDM Mesh Networks (2004)

Vinod Vokkarane, Jianping Wang, Raja Jothi, Xiangtong Qi, Balaji Raghavachari, And Jason Jue

A fault-tolerant scheme, called dual homing, is generally used in IP-based access networks to increase the availability of the network. In dual homing, a host is connected to two different access...

Optimal Placement of NAK-Suppressing Agents for Reliable Multicast: A Partial Deployment Case (2004)

Ovidiu Daescu, Raja Jothi, Balaji Raghavachari, And Kamil Sarac, Kamil Sarac

Ovidiu Daescu Raja Jothi Balaji Raghavachari Kamil Sarac Department of Computer Science University of Texas at Dallas Richardson, TX 75083, USA [daescu, raja, rbk, ksarac]@utdallas.edu ABSTRACT In...

Placement of Proxy Servers to Support Server-Based Reliable Multicast (2004)

Approximation algorithms for finding low-degree subgraphs (2004)

We consider the problem of placing k proxies on a n node network to support server-based reliable multicast. Typically, in a multicast connection, the sender transmits information to all the...

Philip N. Klein, Radha Krishnan, Balaji Raghavachari, R. Ravi

We give quasipolynomial-time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connectivity is specified by “proper ”...

Dynamic capacitated minimum spanning trees (2004)

Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design (2004)

Abstract — Given a set of terminals, each associated with a positive number denoting the traffic to be routed to a central terminal (root), the Capacitated Minimum Spanning Tree (CMST) problem asks...

Balaji Raghavachari

Abstract. Given an undirected graph G = (V, E) with nonnegative costs on its edges, a root node r ∈ V,aset of demands D ⊆ V with demand v ∈ D wishing to route w(v) units of flow (weight) to r,...

Degree-Bounded Minimum Spanning Trees (2004)

A 5/4-Approximation Algorithm for Minimum 2-Edge-Connectivity (2003)

Given n points in the Euclidean plane, the degree- minimum spanning tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most . The problem is NP-hard for...

Raja Jothi, Balaji Raghavachari, Subramanian Varadarajan

A 5/4-approximation algorithm is presented for the minimum cardinality 2-edge-connected spanning subgraph problem in undirected graphs. This improves the previous best approximation ratio of 4/3. It...

Designing Multi-Commodity Flow Trees (2002)

Khuller, Samir, Raghavachari, Balaji, Young, Neal E.

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 considers the...

Approximating the Minimum Equivalent Digraph (2002)

Khuller, Samir, Raghavachari, Balaji, Young, Neal E.

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 NP-hard. This paper...

Low-Degree Spanning Trees of Small Weight (2002)

Khuller, Samir, Raghavachari, Balaji, Young, Neal E.

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-known Christofides...

Balancing Minimum Spanning and Shortest Path Trees (2002)

Khuller, Samir, Raghavachari, Balaji, Young, Neal E.

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 tree. The algorithm...

On Strongly Connected Digraphs with Bounded Cycle Length (2002)

The directed minimum-degree spanning tree problem (2001)

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 NP-hard. This paper...

Radha Krishnan, Balaji Raghavachari

Abstract. Consider a directed graph G =(V,E) with n vertices and a root vertex r ∈ V. The DMDST problem for G is one of constructing a spanning tree rooted at r, whose maximal degree is the...

The directed minimum-degree spanning tree problem (2001)

Balaji Raghavachari, Log N

Given a directed graph G = (V; E) with n vertices and a root vertex r 2 V, consider the problem of constructing a spanning tree rooted at r (also known as a branching) whose maximal degree is the...

Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem (2000)

Nili Guttmann-beck, Refael Hassin, Samir Khuller, Balaji Raghavachari

z

Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem (2000)

Nili Guttmann-beck, Refael Hassin, Samir Khuller, Balaji Raghavachari

Let G = (V; E) be a complete undirected graph with vertex set V , edge set E, and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V 1 ; : : : ; V k ....

A Uniform Framework for Approximating Weighted Connectivity Problems (1999)

Samir Khuller, Balaji Raghavachari, An Zhu

We introduce a new algorithmic technique that applies to several graph connectivity problems. Its power is demonstrated by experimental studies of the minimum-weight strongly-connected spanning...

Algorithms for capacitated vehicle routing (1998)

Moses Charikar, Samir Khuller, Balaji Raghavachari

Given n identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to n target locations (slots) with a vehicle that can carry at most k...

The Finite Capacity Dial-A-Ride Problem (1998)

Moses Charikar, Balaji Raghavachari

We give the rst non-trivial approximation algorithm for the Capacitated Dial-a-Ride problem: given a collection of objects located at points in a metric space, a specied destination point for each...

Algorithms for Capacitated Vehicle Routing (1998)

Moses Charikar, Samir Khuller, Balaji Raghavachari

Given n identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to n target locations (slots) with a vehicle that can carry at most k...

Approximation Algorithms for Mixed Postman Problem (1998)

Balaji Raghavachari, Jeyakesavan Veerasamy

The mixed postman problem, a generalization of the Chinese postman problem, is that of finding a shortest tour that traverses each edge of a given mixed graph (a graph containing both undirected and...

Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem (1998)

Nili Guttmann-beck, Refael Hassin, Samir Khuller, Balaji Raghavachari

Let G = (V, E) be a complete undirected graph with vertex set V , edge set E, and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V 1 , ..., V k . The...

Algorithms for Capacitated Vehicle Routing (1997)

Charikar, Moses, Khuller, Samir, Raghavachari, Balaji

Given $n$ identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to $n$ target locations (slots) with a vehicle that can carry at...

Algorithms for Capacitated Vehicle Routing (1997)

Charikar, Moses, Khuller, Samir, Raghavachari, Balaji

Given $n$ identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to $n$ target locations (slots) with a vehicle that can carry at...

A network-flow technique for finding low-weight bounded-degree spanning trees (1997)

S'andor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young

4 z

A network-flow technique for finding low-weight bounded-degree spanning trees (1997)

S'andor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young

Given 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...

A Network Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1997)

Sandor P. Fekete, S'andor P. Fekete, Samir Khuller, Samir Khuller, Monika Klemmstein, Monika Klemmstein, ...

Given 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...

Improved Approximation Algorithms for Uniform Connectivity Problems (1996)

Samir Khuller, Balaji Raghavachari

The problem of finding minimum weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial...

On strongly connected digraphs with bounded cycle length (1996)

Graph and Network Algorithms (1996)

Given a directed graph G = (V; E), a natural problem is to choose a minimum number of the edges in E such that, for any two vertices u and v, if there is a path from u to v in E, then there is a path...

Samir Khuller, Balaji Raghavachari

INTRODUCTION Graphs provide a powerful tool to model objects and relationships among objects. The study of graphs dates back to Euler 's days in the 18th century, when he defined the Konigsberg...

A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1995)

Fekete, Sandor P., Khuller, Samir, Klemmstein, Monika, Raghavachari, Balaji, Young, Neal

Given 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...

A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1995)

Fekete, Sandor P., Khuller, Samir, Klemmstein, Monika, Raghavachari, Balaji, Young, Neal

Given 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...

Improved Approximation Algorthmsor Uniform Connectivity Problems (1995)

Khuller, Samir, Raghavachari, Balaji

The problem of finding minimum weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial...

Improved Approximation Algorthmsor Uniform Connectivity Problems (1995)

Khuller, Samir, Raghavachari, Balaji

The problem of finding minimum weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial...

Balancing Minimum Spanning Trees and Shortest-Path Trees (1995)

Samir Khuller, Balaji Raghavachari, Penn State, Neal Young

Abstract We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous trade-off: given the...

Improved Approximation Algorithms for Uniform Connectivity Problems (1995)

Samir Khuller, Balaji Raghavachari

The problem of finding minimum weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial...

A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1995)

Sandor P. Fekete, Samir Khuller, Monika Klemmstein, Neal Young, Balaji Raghavachari, Balaji Raghavachari

Given 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...

BOUNDED-DEGREE TREES USING NETWORK FLOW 311 (1995)

Or P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young

pp. 105�117.

Localization in Graphs (1994)

Khuller, Samir, Raghavachari, Balaji, Rosenfeld, Azriel

Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a ``graph space''. The robot can locate...

Localization in Graphs (1994)

Khuller, Samir, Raghavachari, Balaji, Rosenfeld, Azriel

Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a ``graph space''. The robot can locate...

Low Degree Spanning Trees of Small Weight (1994)

On Strongly Connected Digraphs with Bounded Cycle Length (1994)

Given 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...

Low Degree Spanning Trees of Small Weight (1994)

The 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...

On Strongly Connected Digraphs with Bounded Cycle Length (1994)

Given 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...

Approximating the minimum-degree Steiner tree to within one of optimal (1994)

The 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...

Balaji Raghavachari

some optimal tree for the respective problems. Unless P = N P, this is the best bound achievable in polynomial time.

Designing multi-commodity flow trees (1994)

Designing Multi-Commodity Flow Trees (1994)

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 considers the...

Samir Khuller Balaji, Balaji Raghavachari, Neal Young

The traditional multi-commodity ow problem assumes a given ow network in which multiple commodities are to be maximally routed in response to given demands. This paper considers the multi-commodity...

Maintaining Directed Reachability with Few Edges (1993)

Maintaining Directed Reachability with Few Edges (1993)

The 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...

Designing Multi-Commodity Flow Trees (1993)

The 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...

Designing Multi-Commodity Flow Trees (1993)

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 considers the...