Refereed Journal Papers

  1. Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle
    Surender Baswana, Koustav Bhanja, Abhyuday Pandey
    ACM Transactions on Algorithms , 19(4): 38:1-38:41, 2023.


  2. Mincut Sensitivity Data Structure for the Insertion of an Edge.
    Surender Baswana, Shiv Kumar Gupta, and Till Knollmann
    Algorithmica, 84(9): 2702-2734.


  3. Fault Tolerant Depth First Search in Undirected Graps: Simple Yet Efficient
    Surender Baswana, Shiv Kumar Gupta, and Ayush Tulsyan
    Algorithmica, 84(7): 2028-2049, 2022.


  4. Approximate Single-Source Fault Tolerant Shortest Path
    Surender Baswana, Keerti Choudhary, Moazzam Hussain, Liam Roditty
    ACM Transactions on Algorithms , 16(4): 44:1-44:22, 2020.


  5. Dynamic DFS in undirected graphs: Breaking the O(m) barrier
    Surender Baswana, Shreejit Ray Chaudhury, Keerti choudhary, and Shahbaz Khan
    SIAM Journal on Computing, 48(4), 1335-1363, 2019.


  6. Centralized Admissions for Engineering Colleges in India
    Surender Baswana, Partha P. Chakrabarti, Sharat Chandran, Yashodhan Kanoria, Utkarsh Patange
    Interfaces, 49(5), 338-354, 2019.
    (A special issue for the finalist for the Wagner Prize for Excellence in Operations Research Practice 2018).


  7. An efficient strongly connected components algorithm in fault tolerant model
    Surender Baswana, Keerti choudhary, and Liam Roditty
    Algorithmica 81(3): 967-985, 2019.


  8. Fully dynamic maximal matching in O(log n) update time (corrected version).
    Surender Baswana, Manoj Gupta, and Sandeep Sen.
    SIAM Journal on Computing, 47(3), 617-650, 2018.
    DOI:   https://epubs.siam.org/doi/abs/10.1137/16M1106158
    Note: This result first appeared in SIAM Journal on Computing 44(1): 88-113, 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 that has been published in SIAM Journal on Computing after a thorough peer review process.


  9. Fault-tolerant subgraph for single-source reachability: General and optimal.
    Surender Baswana, Keerti Choudhary, and Liam Roditty
    SIAM Journal on Computing, 47(1), 80-95, 2018.


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


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


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


  13. Faster Algorithms for All-Pairs Approximate Shortest Paths in Undirected Graphs.
    Surender Baswana and Telikepalli Kavitha
    SIAM Journal on Computing, volume 39, issue 7, pp 2865-2896 (2010).


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


  15. All-Pairs Nearly 2-Approximate Shortest Paths in O(n2 polylog n) time.
    Surender Baswana, Vishrut Goyal, and Sandeep Sen.
    Theoretical Computer Science, volume 410, issue 1, pp 84-93 (2009).


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


  17. 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 532-563, 2007.


  18. Improved Decremental Algorithms for Maintaining Transitive Closure and All-pairs Shortest Paths in Digraphs
    Surender Baswana, Ramesh Hariharan, and Sandeep Sen
    Journal of Algorithms, volume 62, issue 2, pp 74-92, 2007.


  19. 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 557-577, 2006.
    Special issue for selected best papers that appeared in SODA 2004


  20. Planar Graph Blocking for External Searching
    Surender Baswana and Sandeep Sen
    Algorithmica, volume 34, pp 298-308, 2002.


Refereed Conference Papers

  1. Vital Edges for (s,t)-mincuts: Efficient Algorithms, Compact Structures, and Optimal Sensitivity Oracles.
    with Koustav Bhanja
    Proc. 52nd International Colloquium on Automata, Languages, and Programming (ICALP), 17:1-17:20, 2024.


  2. Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle.
    with Koustav Bhanja and Abhyuday Pandey
    Proc. 50th International Colloquium on Automata, Languages, and Programming (ICALP), 15:1-15:20, 2022.


  3. Sensitivity Oracles for All-Pairs Mincuts.
    with Abhyuday Pandey
    Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 581-609, 2022.


  4. Mincut Sensitivity Data Structures for the Insertion of an Edge
    with Shiv Gupta and Till Knollmann
    Proc. 28th European Symposium on Algorithms (ESA), 12:1-12:14, 2020


  5. Fault tolerant and fully dynamic DFS in undirected graphs: Simple yet efficient
    with Shiv Gupta and Ayush Tulsyan
    Proc. 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), 65:1-65:16, 2019.


  6. Centralized admissions for engineering colleges in India
    with Partha P. Chakrabarti, Sharat Chandran, Yashodhan Kanoria, and Utkarsh Patange
    Proc. of 20th ACM Conference on Economics and Computation (EC), 323-324, 2019.


  7. Approximate single source fault tolerant shortest path.
    with Keerti Choudhary, Moazzam Hussain, and Liam Roditty
    Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1901-1915, 2018.


  8. Incremental DFS algorithms: a theoretical and experimental study.
    with Ayush Goel and Shahbaz Khan
    Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), 53-72, 2018.


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


  10. 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.


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


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


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


  14. 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 138-149, 2014.


  15. 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), 257-266,~2012.


  16. 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.


  17. 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 383-392, 2011.


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


  19. 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 609-621, 2008


  20. 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 94-106, 2008.


  21. Fully Dynamic Algorithms for Graph Spanners with Poly-Logaritmic Update Time
    with S. Sarkar
    Proc. 19th Symposium on Discrete Algorithms (SODA)
    pp 672-681. ACM and SIAM, 2008.


  22. Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths
    with T. Kavitha
    Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS)
    IEEE, pp 591-602, 2006.


  23. Dynamic Algorithms for Graph Spanners
    S. Baswana
    Proc. 14th European Symposium on Algorithms (ESA)
    Springer-Verlag, Lecture Notes in Computer Science, volume 4168, pp 76-87, 2006.


  24. 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 672-681, 2005.


  25. All-Pairs Nearly 2-Approximate 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)
    Springer-Verlag, Lecture Notes in Computer Science, volume 3404, pp 666-679, 2005.


  26. 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 264-273, 2004.


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


  28. Maintaining All-pairs Approximate Shortest Paths under Deletion of Edges
    with R. Hariharan, and S. Sen
    Proc. 14th Symposium on Discrete Algorithms (SODA)
    ACM and SIAM, pp 394-403, 2003.


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


  30. Planar Graph Blocking for External Searching
    with S. Sen
    Proc. 20th Symposium on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
    Springer-Verlag, Lecture Notes in Computer Science, volume 1974, pp 262-263, 2000.


Book Chapters

  1. Randomized graph data-structures 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.

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