Refereed Journal Papers

Fully dynamic maximal matching in O(log n) update time (corrected version).
Surender Baswana, Manoj Gupta, and Sandeep Sen.
Accepted for publication in SIAM Journal on Computing (notification of acceptance received on 29th December 2017).
Note: This result first appeared in
SIAM Journal on Computing 44(1): 88113, 2015. Unfortunately, the
analysis of the algorithm was erroneous. However, we have been able to fix
the error in the analysis based on an interesting property
of the original algorithm that was not reported earlier. The performance
bounds of the original algorithm is preserved in the new analysis.
The pdf file available above is the complete and correct version. It has recently been accepted for publication in SIAM Journal on Computing after a
thorough peer review process.

Faulttolerant subgraph for singlesource reachability: General and optimal.
Surender Baswana, Keerti Choudhary, and Liam Roditty
Accepted for publication in SIAM Journal on Computing, (notification for acceptance received on 25th Septemebr 2017).

Incremental algorithm for DFS tree in undirected graphs
Surender Baswana and Shahbaz Khan
Algorithmica 79(2), 466483, 2017.

Approximate Shortest paths avoiding a failed vertex : near optimal
data structures for undirected unweighted graphs.
Surender Baswana and Neelesh Khanna.
Algorithmica, 66(1): 1850, 2013

Fully Dynamic Randomized Algorithms for Graph Spanners.
Surender Baswana, Sumeet Khurana, and Soumojit Sarkar
ACM Transaction on Algorithms, volume 8(4): 35, 2012

Faster Algorithms for AllPairs Approximate Shortest Paths in Undirected
Graphs.
Surender Baswana and Telikepalli Kavitha
SIAM Journal on Computing, volume 39, issue 7, pp 28652896 (2010).

Additive Spanners and (alpha,beta)Spanners.
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie.
ACM Transaction on Algorithms, volume 7, issue 1, 2010 .

AllPairs Nearly 2Approximate Shortest Paths in O(n^{2} polylog n)
time.
Surender Baswana, Vishrut Goyal, and Sandeep Sen.
Theoretical Computer Science, volume 410, issue 1, pp 8493 (2009).

Streaming Algorithm for
Graph Spanners  Single Pass and Constant Processing Time per Edge
Surender Baswana
Information Processing Letters , volume 106, issue 3, pp 110114,
2008.

A Simple and Linear Time
Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs
Surender Baswana and Sandeep Sen
Random Strutcures and Algorithms, volume 30, issue 4, pp 532563, 2007.

Improved Decremental Algorithms for
Maintaining Transitive Closure and Allpairs Shortest Paths in
Digraphs
Surender Baswana, Ramesh Hariharan, and Sandeep Sen
Journal of Algorithms, volume 62, issue 2, pp 7492, 2007.

Approximate Distance oracles for
Unweighted Graphs in Expected O(n^2) Time
Surender Baswana and Sandeep Sen
ACM Transactions on Algorithms, volume 2, issue 4, pp 557577, 2006.
Special issue for selected best papers that appeared in SODA 2004

Planar Graph Blocking for
External Searching
Surender Baswana and Sandeep Sen
Algorithmica, volume 34, pp 298308, 2002.
Refereed Conference Papers

An efficient strongly connected components algorithm in the faulttolerant model.
with Keerti Choudhary and Liam Roditty.
Proc. of 42nd International Colloquium on Automata, Languages, and Programming (ICALP), 72:1  72:15, 2017.

Fault Tolerant Subgraph for Single Source Reachability:
Generic and Optimal.
with Keerti Choudhary and Liam Roditty.
Proc. 48th ACM Symposium on Theory of Computing (STOC), 2016.

Dynamic DFS Tree in Undirected Graphs: Breaking the O(m) barrier.
with Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan
Proc. 27th ACMSIAM Symposium on Discrete Algorithms (SODA), 2016.

Fault Tolerant Reachability for Directed Graphs
with Keerti Choudhary and Liam Roditty
Proc. 29th International Symposium on Distributed Computing (DISC), pp 528543, 2015.

On Dynamic DFS Tree in Directed Graphs
with Keerti Choudhary
Proc. 40th International Symposium on Mathematical Foundations of Computer Science (MFCS)(2), pp 102114, 2015.

Incremental Algorithm for Maintaining a DFS Tree in an Undirected Graph
with Shahbaz Khan.
Proc. of 41st International Colloquium on Automata, Languages, and Programming (ICALP),pp 138149, 2014.

Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs.
with Abhash Anand, Manoj Gupta, and Sandeep Sen.
Proc. 32nd Symposium on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 257266,~2012.

Single source distance oracle for planar digraphs avoiding any failed node or link
with Utkarsh Lath and Anuradha S. Mehta
Proc. 23rd ACMSIAM Symposium on Discrete Algorithms (SODA), pp 223232, 2012.

Fully dynamic maximal matching in O(log n) update time
with Manoj Gupta and Sandeep Sen
Proc. 52nd IEEE Symposium on Foundations of Computer Science (FOCS), pp 383392, 2011.

Approximate shortest paths oracle handling single vertex
failure
with Neelesh Khanna
Proc. 27th Symposium on Theoretical Aspects of Computer Science
(STACS), pp 513524, 2010.

Distance oracles for unweighted graphs : breaking the quadratic
barrier with constant additive error
with Akshay Gaur, Sandeep Sen, and Jayant Upadhyay
Proc. 35th International Colloquium on Automata, Languages and
Programming (ICALP)
Springer Verlag, Lecture notes in computer science, volume 5125, pp
609621, 2008

Implied Set Closure and Its Application to Memory Consistency Verification
with S. Mehta, V. Powar
Proc. 20th International Conference on Computer Aided Verification
(CAV)
Springer Verlag, Lecture notes in computer science, volume 5123, pp
94106, 2008.

Fully Dynamic Algorithms for Graph Spanners with PolyLogaritmic
Update Time
with S. Sarkar
Proc. 19th Symposium on Discrete Algorithms (SODA)
pp 672681. ACM and SIAM, 2008.

Faster Algorithms for Approximate Distance Oracles and AllPairs Small Stretch Paths
with T. Kavitha
Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS)
IEEE, pp 591602, 2006.

Dynamic Algorithms for Graph Spanners
S. Baswana
Proc. 14th European Symposium on Algorithms (ESA)
SpringerVerlag, Lecture Notes in Computer Science, volume 4168, pp 7687, 2006.

New Construction of (a,b)Spanners and Purely Additive Spanners
with T. Kavitha, K. Mehlhorn, and S. Pettie
Proc. 16th Symposium on Discrete Algorithms (SODA)
ACM and SIAM, pp 672681, 2005.

AllPairs Nearly 2Approximate Shortest Paths in O(n^2 polylog n) Time
with V. Goyal, and S. Sen.
Proc. 22nd Symposium on Theoretical Aspects of Computer Science
(STACS)
SpringerVerlag, Lecture Notes in Computer Science, volume 3404, pp 666679,
2005.

Approximate Distance Oracles for Unweighted Graphs in O(n^2 log n) Time
with S. Sen
Proc. 15th Symposium on Discrete Algorithms (SODA)
ACM and SIAM, pp 264273, 2004.

A Simple Linear Time Algorithms for Computing (2k1)spanner
of Size O(kn^{1+1/k}) for Weighted Graphs
with S. Sen
Proc. 30th International Colloquium on Automata, Languages and Programming
(ICALP)
SpringerVerlag, Lecture Notes in Computer Science, volume 2719, pp 384396, 2003.

Maintaining Allpairs Approximate Shortest Paths under Deletion of Edges
with R. Hariharan, and S. Sen
Proc. 14th Symposium on Discrete Algorithms (SODA)
ACM and SIAM, pp 394403, 2003.

Improved Decremental Algorithms for Transitive Closure and Allpairs
Shortest Paths in Digraphs
with R. Hariharan, and S. Sen
Proc. 34th Symposium on Theory of Computing (STOC)
ACM, pp 117123, 2002.

Planar Graph Blocking for External Searching
with S. Sen
Proc. 20th Symposium on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
SpringerVerlag, Lecture Notes in Computer Science, volume 1974, pp 262263, 2000.
Book Chapters

Randomized graph datastructures for approximate shortest path problem
S. Baswana and S. Sen
Handbook of Data Structures and Applications, ISBN 1584884355. Dinesh Mehta and Sartaj Sahni (Ed.), CRC Press, 2004.

Simple Algorithms for Spanners in
Weighted Graphs
S. Baswana and S. Sen
Encyclopedia of Algorithms. Ming Yang Kao (Ed.), Springer, 2008.