Surender Baswana: Publications
Journal Papers
A Simple and Linear Time Randomized Algorithm for Computing
Sparse Spanners in Weighted Graphs
with Sandeep Sen
in Random Strutcures and Algorithms (to appear)
[
Paper as PS]
Approximate Distance oracles for Unweighted Graphs in Expected O(n^2)
Time
with Sandeep Sen
in ACM Transactions on Algorithms (to appear)
Special issue for selected best papers
that appeared in SODA 2004
[
Paper as PS]
Improved Decremental Algorithms for Maintaining
Transitive Closure and All-pairs Shortest Paths in Digraphs
with Ramesh Hariharan and Sandeep Sen
in Journal of Algorithms (article in press)
[
Paper as PS]
Planar Graph Blocking for External Searching
with Sandeep Sen
in Algorithmica (2002)
34: 298--308
Conference Papers
Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths
with Telikelalli Kavitha
in FOCS 2006 (to appear)
Dynamic Algorithms for Graph Spanners
in ESA 2006 (to appear)
New Construction of (a,b)-Spanners and Purely Additive Spanners
with Telikepalli Kavitha, Kurt Mehlhorn and Seth Pettie
in SODA 2005
All-Pairs Nearly 2-Approximate Shortest Paths
in O(n^2 polylog n) Time
with Vishrut Goyal and Sandeep Sen
in STACS 2005
Approximate Distance Oracles for
Unweighted Graphs in O(n^2 log n) Time
with Sandeep Sen
in SODA 2004
A Simple Linear Time Algorithms for Computing (2k-1)-spanner
of Size O(kn^{1+1/k}) for Weighted Graphs
with Sandeep Sen
in ICALP 2003
Maintaining All-pairs Approximate Shortest
Paths under Deletion of Edges.
with Ramesh Hariharan and Sandeep Sen
in SODA 2003
Improved Decremental Algorithms for Transitive Closure and All-pairs
Shortest Paths in Digraphs
with Ramesh Hariharan and Sandeep Sen
in STOC 2002
Planar Graph Blocking for External Searching
with Sandeep Sen
in FSTTCS 2000
