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...
© 2002 Springer-Verlag New York Inc. Planar Graph Blocking for External Searching 1 (2009)
Abstract. We present a new scheme for storing a planar graph in external memory so that any online path can be traversed in an I-O efficient way. Our storage scheme significantly improves the...
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¨� �...
Let G = (V, E) be an undirected weighted graph on |V | = n vertices, and |E | = m edges. A t-spanner of the graph G, for any t ≥ 1, is a subgraph (V, ES), ES ⊆ E, such that the distance between...
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...
������������ � Let be an undirected graph � on vertices, and ���������� � let denote the distance � in between two � vertices � and. Thorup and...
We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges. For the problem of transitive closure, the previous best...
Surender Baswana, Ramesh Hariharan, Sandeep Sen
We present improved algorithms for maintaining transitive closure and all-pairs shortest paths in a digraph under deletion of edges. For the problem of transitive closure, the previous best known...
Baswana, Surender, Sen, Sandeep
Let G = (V,E) be an undirected weighted graph on |V | = n vertices and |E| = m edges. A t-spanner of the graph G, for any t 1, is a subgraph (V,ES), ES E, such that the distance between any pair of...
Faster Streaming algorithms for graph spanners (2006)
Given an undirected graph $G=(V,E)$ on $n$ vertices, $m$ edges, and an integer $t\ge 1$, a subgraph $(V,E_S)$, $E_S\subseteq E$ is called a $t$-spanner if for any pair of vertices $u,v \in V$, the...
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)...
Faster algorithms for approximate distance oracles and all-pairs small stretch paths (2006)
Let G =(V,E) be a weighted undirected graph with |V | = n and |E | = m. An estimate ˆ δ(u, v) of the distance δ(u, v) in G between u, v ∈ V is said to be of stretch t iff δ(u, v) ≤ ˆ δ(u,...
Faster algorithms for approximate distance oracles and all-pairs small stretch paths (2006)
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)...
All-pairs nearly 2approximate shortest paths in O(n 2 polylog n) time (2005)
Surender Baswana, Vishrut Goyal, Eep Sen
Abstract. Let G(V, E) be an unweighted undirected graph on |V | = n vertices. Let δ(u, v) denote the shortest distance between vertices u, v ∈ V. An algorithm is said to compute all-pairs...
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...
New Constructions of (alpha, beta)-Spanners and Purely Additive Spanners (2005)
Baswana, Surender, Kavitha, Telikepalli, Mehlhorn, Kurt, Pettie, Seth
All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time (2005)
Baswana, Surender, Goyal, Vishrut, Sen, Sandeep, Diekert, Volker, Durand, Bruno
Let $G=(V,E)$ be an unweighted undirected graph on $n$ vertices. Let $\delta(u,v)$ denote the distance between vertices $u,v\inV$. An algorithm is said to compute all-pairs $t$-approximate shortest...
Approximate distance oracle for unweighted graphs in Õ(n²) time (2004)
Let G(V, E) be an undirected weighted graph with |V| = n, |E| = m. Recently Thorup and Zwick introduced a remarkable data-structure that stores all pairs approximate distance information implicitly...
Baswana, Surender, Hariharan, Ramesh, Sen, Sandeep
This paper presents improved algorithms for the following problem: given an unweighted directed graph G(V,E) and a sequence of on-line shortest-path/reachability queries interspersed with...
Randomized graph data-structures for approximate shortest path problem (2004)
Baswana, Surender, Sen, Sandeep, Sahni, Sartaj, Mehta, Dinesh
Approximate distance oracle for unweighted graphs in Õ(n²) time (2004)
Baswana, Surender, Sen, Sandeep
Let G(V, E) be an undirected weighted graph with |V| = n, |E| = m. Recently Thorup and Zwick introduced a remarkable data-structure that stores all pairs approximate distance information implicitly...
Approximate distance oracle for unweighted graphs in Õ(n²) time (2004)
Baswana, Surender, Sen, Sandeep
Let G(V, E) be an undirected weighted graph with |V| = n, |E| = m. Recently Thorup and Zwick introduced a remarkable data-structure that stores all pairs approximate distance information implicitly...
Randomized graph data-structures for approximate shortest path problem (2004)
Baswana, Surender, Sen, Sandeep, Sahni, Sartaj, Mehta, Dinesh
Surender Baswana, Ramesh Hariharan B, Eep Sen A
decremental algorithms for maintaining transitive closure and all-pairs shortest paths A
) edges are required in the worst case for any (2k \Gamma 1)-spanner, which has been proved for k = 1; 2; 3; 5. There exist polynomial time algorithms that can construct spanners with the size that...
A Simple Linear Time Algorithm for Computing Sparse Spanners in Weighted Graphs (2003)
Let G(V; E) be an undirected weighted graph with jV j = n, and jEj = m. A t-spanner of the graph G(V; E) is a sub-graph G(V; ES ), ES E, such that the distance between any pair of vertices in the...
Baswana, Surender, Sen, Sandeep, Hariharan, Ramesh
We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges.(MATH) For the problem of transitive closure, the...
Baswana, Surender, Sen, Sandeep, Hariharan, Ramesh
We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges.(MATH) For the problem of transitive closure, the...