Source author record

Srivathsan Srinivasagopalan

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

On Strong Graph Partitions and Universal Steiner Trees

We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph $G$ and a root node $r$ , we seek a single spanning tree $T$ of minimum {\em stretch}, where the stretch of $T$ is defined to be the maximum ratio, over all terminal sets $X$ , of the cost of the minimal sub-tree $T_X$ of $T$ that connects $X$ to $r$ to the cost of an optimal Steiner tree connecting $X$ to $r$ in $G$ . Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. We provide a polynomial time \ust\ construction for general graphs with $2^{O(\sqrt{\log n})}$ -stretch. We also give a polynomial time $\polylog(n)$-stretch construction for minor-free graphs. One basic building block of our algorithms is a hierarchy of graph partitions, each of which guarantees small strong diameter for each cluster and bounded neighbourhood intersections for each node. We show close connections between the problems of constructing USTs and building such graph partitions. Our construction of partition hierarchies for general graphs is based on an iterative cluster merging procedure, while the one for minor-free graphs is based on a separator theorem for such graphs and the solution to a cluster aggregation problem that may be of independent interest even for general graphs. To our knowledge, this is the first subpolynomial-stretch ( $o(n^ε)$ for any $ε> 0$ ) UST construction for general graphs, and the first polylogarithmic-stretch UST construction for minor-free graphs.

preprint2010arXiv

An Oblivious Spanning Tree for Buy-at-Bulk Network Design Problems

We consider the problem of constructing a single spanning tree for the single-source buy-at-bulk network design problem for doubling-dimension graphs. We compute a spanning tree to route a set of demands (or data) along a graph to or from a designated root node. The demands could be aggregated at (or symmetrically distributed to) intermediate nodes where the fusion-cost is specified by a non-negative concave function $f$ . We describe a novel approach for developing an oblivious spanning tree in the sense that it is independent of the number of data sources (or demands) and cost function at intermediate nodes. To our knowledge, this is the first paper to propose a single spanning tree solution to this problem (as opposed to multiple overlay trees). There has been no prior work where the tree is oblivious to both the fusion cost function and the set of sources (demands). We present a deterministic, polynomial-time algorithm for constructing a spanning tree in low doubling graphs that guarantees $\log^{3}D\cdot\log n$ -approximation over the optimal cost, where $D$ is the diameter of the graph and $n$ the total number of nodes. With constant fusion-cost function our spanning tree gives a $O(\log^3 D)$ -approximation for every Steiner tree to the root.

preprint2010arXiv

Oblivious Buy-at-Bulk in Planar Graphs

In the oblivious buy-at-bulk network design problem in a graph, the task is to compute a fixed set of paths for every pair of source-destinations in the graph, such that any set of demands can be routed along these paths. The demands could be aggregated at intermediate edges where the fusion-cost is specified by a canonical (non-negative concave) function $f$ . We give a novel algorithm for planar graphs which is oblivious with respect to the demands, and is also oblivious with respect to the fusion function $f$ . The algorithm is deterministic and computes the fixed set of paths in polynomial time, and guarantees a $O(\log n)$ approximation ratio for any set of demands and any canonical fusion function $f$ , where $n$ is the number of nodes. The algorithm is asymptotically optimal, since it is known that this problem cannot be approximated with better than $Ω(\log n)$ ratio. To our knowledge, this is the first tight analysis for planar graphs, and improves the approximation ratio by a factor of $\log n$ with respect to previously known results.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.