Abstract New Constructions of (α, β)-Spanners and Purely Additive Spanners ∗ (2009)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An (α, β)-spanner of an unweighted graph G is a subgraph H that approximates distances in G in the following sense. For any two vertices u, v: δH(u, v) ≤ αδG(u, v) + β, where δG is the...
Abstract Popular Matchings (2008)
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in order of preference, possibly involving...
Robert W. Irving Rank-Maximal Matchings (2008)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
Suppose that each member of a set ¡ of applicants ranks a subset of a set of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
New Constructions of ¡ β ¢ α-Spanners and Purely Spanners£ Additive (2008)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An ¦ α § β ¨-spanner of an unweighted graph G is a subgraph H that approximates distances in G in the following sense. For any two vertices u § v: δH ¦ u § v¨� © αδG ¦ u § v¨� �...
An (O)over-tilde (m(2)n) Algorithm for Minimum Cycle Basis of Graphs (2008)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios, Paluch, Katarzyna E
We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated...
Additive Spanners and (α, β)-Spanners ∗ (2008)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a...
An Õ(m2 n) algorithm for Minimum Cycle Basis of graphs ∗ (2008)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch
We consider the problem of computing a minimum cycle basis in a graph G with m edges and n vertices. The input to this problem is an undirected graph whose edges have non-negative weights. In this...
Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs (2008)
Abstract. Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G....
A Faster Deterministic Algorithm for Minimum Cycle Basis in Directed Graphs (2008)
Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn, Kavitha Kurt Mehlhorn
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is...
An O˜ (m2n) Algorithm for Minimum Cycle Basis of Graphs (2008)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrions, Paluch, Katarzyna E.
Dynamic matrix rank with partial lookahead (2008)
We consider the problem of maintaining information about the rank of a matrix $M$ under changes to its entries. For an $n times n$ matrix $M$, we show an amortized upper bound of $O(n^{omega-1})$...
Faster Algorithms for Minimum Cycle Basis in Directed Graphs (2008)
Hariharan, Ramesh, Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph $G$ whose edges have nonnegative weights. A cycle in this graph is...
Faster Algorithms for Online Topological Ordering (2007)
Kavitha, Telikepalli, Mathew, Rogers
We present two algorithms for maintaining the topological order of a directed acyclic graph with n vertices, under an online edge insertion sequence of m edges. Efficient algorithms for online...
Algorithms to Compute Minimum Cycle Basis in Directed Graphs (2007)
Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have non-negative weights assigned to them. In this problem a {-1,0,1}...
Algorithms to Compute Minimum Cycle Basis in Directed Graphs (2007)
Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have non-negative weights assigned to them. In this problem a {-1,0,1}...
Abraham, David J, Irving, Robert W, Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly involving...
Abraham, David J, Irving, Robert W, Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly involving...
Faster algorithms for online topological ordering (2007)
Telikepalli Kavitha, Rogers Mathew, Telikepalli Kavitha, Rogers Mathew
We present two algorithms for maintaining the topological order of a directed acyclic graph with n vertices, under an online edge insertion sequence of m edges. Efficient algorithms for online...
Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related (2007)
Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi
Given an undirected unweighted graph G =(V,E) andan integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most...
Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related (2007)
Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi
Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the
New approximation algorithms for minimum cycle bases of graphs (2007)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail
We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also...
New approximation algorithms for minimum cycle bases of graphs (2007)
Telikepalli Kavitha, Dimitrios Michail
Abstract. We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also...
New approximation algorithms for minimum cycle bases of graphs (2007)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail
We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this...
An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs (2007)
Bhalgat, Anand, Hariharan, Ramesh, Kavitha, Telikepalli, Panigrahi, Debmalya
We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical...
Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem (2007)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios, Paluch, Katarzyna E.
New Approximation Algorithms for Minimum Cycle Bases of Graphs (2007)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios
We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this...
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs (2006)
Hariharan, Ramesh, Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is...
Efficient algorithms for weighted rank-maximal matchings and related problems (2006)
Kavitha, Telikepalli, Shah, Chintan D
We consider the problem of designing efficient algorithms for computing certain matchings in a bipartite graph , with a partition of the edge set as . A matching is a set of (a, p) pairs, such that...
Efficient algorithms for weighted rank-maximal matchings and related problems (2006)
Kavitha, Telikepalli, Shah, Chintan D
We consider the problem of designing efficient algorithms for computing certain matchings in a bipartite graph , with a partition of the edge set as . A matching is a set of (a, p) pairs, such that...
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs (2006)
Hariharan, Ramesh, Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is...
Dynamic matching markets and voting paths (2006)
David J. Abraham, Telikepalli Kavitha
Abstract. We consider a matching market, in which the aim is to maintain a popular matching between a set of applicants and a set of posts, where each applicant has a preference list, that ranks some...
Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems (2006)
Telikepalli Kavitha, Chintan D. Shah
Abstract. We consider the problem of designing efficient algorithms for computing certain matchings in a bipartite graph G = (A ∪ P, E), with a partition of the edge set as E = E1 ˙ ∪ E2... ˙...
Faster algorithms for approximate distance oracles and all-pairs small stretch paths (2006)
Surender Baswana, Telikepalli Kavitha
Let G = (V, E) be a weighted undirected graph with |V | = n and |E | = m. An estimate ˆ δ(u, v) of the distance δ(u, v) between u, v ∈ V is said to be of stretch t iff δ(u, v) ≤ ˆ δ(u, v)...
A faster deterministic algorithm for minimum cycle basis in directed graphs (2006)
Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn
Abstract. We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph...
Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is...
Irving, Robert W., Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios, Paluch, Katarzyna
Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
An $\~{O}(m^2n)$ randomized algorithm to compute a minimum cycle basis of a directed graph (2005)
We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {−1, 0, 1}...
An $\~{O}(m^2n)$ randomized algorithm to compute a minimum cycle basis of a directed graph (2005)
We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {−1, 0, 1}...
A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs (2005)
Telikepalli Kavitha, Kurt Mehlhorn
Abstract. We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have non-negative weights assigned to them. We give an Õ(m4 n)...
Algorithms to Compute Minimum Cycle Basis in Directed Graphs (2005)
Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have nonnegative weights assigned to them. In this problem a associated with...
New constructions of (α, β)-spanners and purely additive spanners (2005)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An α�β-spanner of an unweighted graph G is a subgraph H that approximates distances in G in the following sense. For any two vertices u�v: δH u�v�αδG u�v β, where δG is the distance...
Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have nonnegative weights assigned to them. In this problem a {−1,0,1}...
A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs (2005)
Kavitha, Telikepalli, Mehlhorn, Kurt, Diekert, Volker, Durand, Bruno
New Constructions of (alpha, beta)-Spanners and Purely Additive Spanners (2005)
Baswana, Surender, Kavitha, Telikepalli, Mehlhorn, Kurt, Pettie, Seth
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
Abstract. We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in order of preference, possibly...
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
Abstract. We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly...
Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
Suppose that each member of a set�of applicants ranks a subset of a set Èof posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of matching a set of applicants to a set of posts, where each applicant ranks a non-empty subset of posts in an order of preference, possibly involving ties. We say that a...
A faster algorithm for minimum cycle basis of graphs (2004)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail
Abstract. In this paper we consider the problem of computing a minimum cycle basis in a graph G with m edges and n vertices. The edges of G have non-negative weights on them. The previous best result...
Strongly Stable Matchings in Time O(nm) (2003)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
An instance of the stable marriage problem is an undirected bipartite graph G = (X [W;E) with linearly ordered adjacency lists; ties are allowed. A matching M is a set of edges no two of which share...