Professor, Department of Computer Science and Engineering
Specialization
Design and analysis of efficient algorithms.
Research Interest
Graph algorithms, randomized algorithms, and dynamic algorithms.
Education
PhD, October 2003(Indian Institute of Technology Delhi, Department of Computer Science). Thesis Title: Efficient randomized algorithms for path problems in graphs Supervisor:Prof. Sandeep Sen
M.Tech, 1999(Indian Institute of Technology Delhi, Department of Computer Science)
B.Tech, 1997(Indian Institute of Technology Delhi, Department of Computer Science)
Incremental Algorithm for Maintaining a DFS Tree in an Undirected Graphwith Shahbaz Khan.Proc. of 41st International Colloquium on Automata, Languages, and Programming (ICALP), 2014.
Fully Dynamic Randomized Algorithms for Graph Spanners.with S. Khurana, and S. Sarkar,ACM Transaction on Algorithms, volume 8(4): 35, 2012
Single source distance oracle for planar digraphs avoiding any failed node or link.with Utkarsh Lath and Anuradha S. Mehta.Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 223-232, 2012.
Fully dynamic maximal matching in O(log n) update timewith Manoj Gupta and Sandeep Sen.Proc. 52nd IEEE Symposium on Foundations of Computer Science (FOCS), pp 383-392, 2011.
Faster Algorithms for All-Pairs Approximate Shortest Paths in Undirected Graphs.with T. Kavitha.SIAM Journal of Computing, volume 39, issue 7, pp 2865-2896 (2010).
S. Baswana, U. Lath, and A. Mehta. Single source distance oracle for planar digraphs avoiding any failed node or link. Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 223-232, 2012.
S. Baswana, M. Gupta, and S. Sen. Fully dynamic maximal matching in O(log n) update time. Proc. 52nd IEEE Symposium on Foundations of Computer Science (FOCS), 383-392, 2011.
S. Baswana, S. Khurana, and S. Sarkar. Fully Dynamic Algorithms for Graph Spanners. ACM Transactions on Algorithms 8(4):35, 2012.
S. Baswana and T. Kavitha. Faster Algorithms for All-Pairs Approximate Shortest Paths in Undirected Graphs. SIAM Journal of Computing 39(7), 2865-2896, 2010.
S. Baswana and N. Khanna. Approximate shortest paths under single vertex failure : Optimal size data structures for unweighted graphs. Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS), 513-524, 2010. [journal version appeared in Algorithmica 66(1),18-50, 2013]