Edit Profile (opens in new tab) Baswana, Surender Co-Author Distance Author ID: baswana.surender Published as: Baswana, Surender Documents Indexed: 49 Publications since 2000 Co-Authors: 33 Co-Authors with 46 Joint Publications 747 Co-Co-Authors all top 5 Co-Authors 3 single-authored 18 Sen, Sandeep 10 Choudhary, Keerti 7 Roditty, Liam 5 Khan, Shahbaz 4 Gupta, Manoj Kumar 4 Gupta, Shiv K. 3 Hariharan, Ramesh 3 Kavitha, Telikepalli 2 Chaudhury, Shreejit Ray 2 Goyal, Vishrut 2 Hussain, Moazzam 2 Khanna, Neelesh 2 Knollmann, Till 2 Mehlhorn, Kurt 2 Pettie, Seth 2 Sarkar, Soumojit 2 Tulsyan, Ayush 1 Anand, Abhash 1 Bhanja, Koustav 1 Biswas, Somenath 1 Doerr, Benjamin 1 Friedrich, Tobias 1 Gaur, Akshay 1 Goel, Ayush 1 Khurana, Sumeet 1 Kurur, Piyush P. 1 Lath, Utkarsh 1 Mehta, Anuradha S. 1 Mehta, Shashank K. 1 Neumann, Frank 1 Pandey, Abhyuday 1 Powar, Vishal 1 Upadhyay, Jayant all top 5 Serials 6 Algorithmica 5 SIAM Journal on Computing 5 ACM Transactions on Algorithms 1 Information Processing Letters 1 Theoretical Computer Science 1 Journal of Algorithms 1 Random Structures & Algorithms Fields 48 Computer science (68-XX) 33 Combinatorics (05-XX) 2 Operations research, mathematical programming (90-XX) 1 Mathematical logic and foundations (03-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 39 Publications have been cited 429 times in 283 Documents Cited by ▼ Year ▼ Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error. Zbl 1153.68405 Baswana, Surender; Gaur, Akshay; Sen, Sandeep; Upadhyay, Jayant 101 2008 A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Zbl 1118.68582 Baswana, Surender; Sen, Sandeep 34 2007 Additive spanners and \(({\alpha}, {\beta})\)-spanners. Zbl 1295.05094 Baswana, Surender; Kavitha, Telikepalli; Mehlhorn, Kurt; Pettie, Seth 32 2010 Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time. Zbl 1321.68214 Baswana, Surender; Sen, Sandeep 25 2006 A simple linear time algorithm for computing a \((2k-1)\)-spanner of \(O(n^{1+1/k})\) size in weighted graphs. Zbl 1039.05056 Baswana, Surender; Sen, Sandeep 19 2003 Fully dynamic randomized algorithms for graph spanners. Zbl 1295.05221 Baswana, Surender; Khurana, Sumeet; Sarkar, Soumojit 16 2012 Fully dynamic maximal matching in \(O(\log n)\) update time. Zbl 1292.68039 Baswana, Surender; Gupta, Manoj; Sen, Sandeep 14 2011 New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners. Zbl 1297.05066 Baswana, Surender; Kavitha, Telikepalli; Mehlhorn, Kurt; Pettie, Seth 14 2005 Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier. Zbl 1410.68277 Baswana, Surender; Chaudhury, Shreejit Ray; Choudhary, Keerti; Khan, Shahbaz 14 2016 Fully dynamic maximal matching in \(O(\log n)\) update time. Zbl 1314.05155 Baswana, Surender; Gupta, Manoj; Sen, Sandeep 13 2015 Computing single source shortest paths using single-objective fitness. Zbl 1369.68296 Baswana, Surender; Biswas, Somenath; Doerr, Benjamin; Friedrich, Tobias; Kurur, Piyush P.; Neumann, Frank 13 2009 Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. Zbl 1120.68114 Baswana, Surender; Hariharan, Ramesh; Sen, Sandeep 11 2007 Faster algorithms for all-pairs approximate shortest paths in undirected graphs. Zbl 1227.05231 Baswana, Surender; Kavitha, Telikepalli 11 2010 Streaming algorithm for graph spanners-single pass and constant processing time per edge. Zbl 1186.68590 Baswana, Surender 11 2008 Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs. Zbl 1264.68068 Baswana, Surender; Khanna, Neelesh 10 2013 Approximate shortest paths avoiding a failed vertex: optimal size data structures for unweighted graphs. Zbl 1230.68063 Khanna, Neelesh; Baswana, Surender 9 2010 Dynamic algorithms for graph spanners. Zbl 1131.68479 Baswana, Surender 7 2006 All-pairs nearly 2-approximate shortest-paths in \(O(n^2\text{ polylog }n)\) time. Zbl 1118.05311 Baswana, Surender; Goyal, Vishrut; Sen, Sandeep 7 2005 On dynamic DFS tree in directed graphs. Zbl 1465.68055 Baswana, Surender; Choudhary, Keerti 7 2015 Approximate distance oracles for unweighted graphs in \(\tilde{\mathcal O}(n^2)\) time. Zbl 1317.68062 Baswana, Surender; Sen, Sandeep 7 2004 Incremental algorithm for maintaining DFS tree for undirected graphs. Zbl 1370.68227 Baswana, Surender; Khan, Shahbaz 6 2014 Fault tolerant subgraph for single source reachability: generic and optimal. Zbl 1376.68103 Baswana, Surender; Choudhary, Keerti; Roditty, Liam 6 2016 Maintaining approximate maximum weighted matching in fully dynamic graphs. Zbl 1354.68289 Anand, Abhash; Baswana, Surender; Gupta, Manoj; Sen, Sandeep 6 2012 Fault tolerant reachability for directed graphs. Zbl 1394.68262 Baswana, Surender; Choudhary, Keerti; Roditty, Liam 5 2015 Incremental DFS algorithms: a theoretical and experimental study. Zbl 1403.68147 Baswana, Surender; Goel, Ayush; Khan, Shahbaz 4 2018 Single source distance oracle for planar digraphs avoiding a failed node or link. Zbl 1422.68044 Baswana, Surender; Lath, Utkarsh; Mehta, Anuradha S. 4 2012 Fully dynamic maximal matching in \(O(\log n)\) update time (corrected version). Zbl 1387.05188 Baswana, Surender; Gupta, Manoj; Sen, Sandeep 3 2018 Fully dynamic algorithm for graph spanners with polylogarithmic update time. Zbl 1192.05150 Baswana, Surender; Sarkar, Soumojit 3 2008 Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient. Zbl 07561709 Baswana, Surender; Gupta, Shiv; Tulsyan, Ayush 3 2019 Maintaining all-pairs approximate shortest path under deletion of edges. Zbl 1094.68603 Baswana, Surender; Hariharan, Ramesh; Sen, Sandeep 2 2003 Incremental algorithm for maintaining a DFS tree for undirected graphs. Zbl 1372.68200 Baswana, Surender; Khan, Shahbaz 2 2017 Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. Zbl 1192.68469 Baswana, Surender; Hariharan, Ramesh; Sen, Sandeep 2 2002 An efficient strongly connected components algorithm in the fault tolerant model. Zbl 1418.68159 Baswana, Surender; Choudhary, Keerti; Roditty, Liam 2 2019 Randomized graph algorithms: techniques and analysis. Zbl 1489.68399 Baswana, Surender; Sen, Sandeep 1 2016 All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time. Zbl 1161.68036 Baswana, Surender; Goyal, Vishrut; Sen, Sandeep 1 2009 Fault-tolerant subgraph for single-source reachability: general and optimal. Zbl 1379.05045 Baswana, Surender; Choudhary, Keerti; Roditty, Liam 1 2018 Planar graph blocking for external searching. Zbl 1016.68032 Baswana, Surender; Sen, Sandeep 1 2002 Mincut sensitivity data structures for the insertion of an edge. Zbl 07572799 Baswana, Surender; Gupta, Shiv; Knollmann, Till 1 2022 Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier. Zbl 1420.05166 Baswana, Surender; Chaudhury, Shreejit Ray; Choudhary, Keerti; Khan, Shahbaz 1 2019 Mincut sensitivity data structures for the insertion of an edge. Zbl 07572799 Baswana, Surender; Gupta, Shiv; Knollmann, Till 1 2022 Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient. Zbl 07561709 Baswana, Surender; Gupta, Shiv; Tulsyan, Ayush 3 2019 An efficient strongly connected components algorithm in the fault tolerant model. Zbl 1418.68159 Baswana, Surender; Choudhary, Keerti; Roditty, Liam 2 2019 Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier. Zbl 1420.05166 Baswana, Surender; Chaudhury, Shreejit Ray; Choudhary, Keerti; Khan, Shahbaz 1 2019 Incremental DFS algorithms: a theoretical and experimental study. Zbl 1403.68147 Baswana, Surender; Goel, Ayush; Khan, Shahbaz 4 2018 Fully dynamic maximal matching in \(O(\log n)\) update time (corrected version). Zbl 1387.05188 Baswana, Surender; Gupta, Manoj; Sen, Sandeep 3 2018 Fault-tolerant subgraph for single-source reachability: general and optimal. Zbl 1379.05045 Baswana, Surender; Choudhary, Keerti; Roditty, Liam 1 2018 Incremental algorithm for maintaining a DFS tree for undirected graphs. Zbl 1372.68200 Baswana, Surender; Khan, Shahbaz 2 2017 Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier. Zbl 1410.68277 Baswana, Surender; Chaudhury, Shreejit Ray; Choudhary, Keerti; Khan, Shahbaz 14 2016 Fault tolerant subgraph for single source reachability: generic and optimal. Zbl 1376.68103 Baswana, Surender; Choudhary, Keerti; Roditty, Liam 6 2016 Randomized graph algorithms: techniques and analysis. Zbl 1489.68399 Baswana, Surender; Sen, Sandeep 1 2016 Fully dynamic maximal matching in \(O(\log n)\) update time. Zbl 1314.05155 Baswana, Surender; Gupta, Manoj; Sen, Sandeep 13 2015 On dynamic DFS tree in directed graphs. Zbl 1465.68055 Baswana, Surender; Choudhary, Keerti 7 2015 Fault tolerant reachability for directed graphs. Zbl 1394.68262 Baswana, Surender; Choudhary, Keerti; Roditty, Liam 5 2015 Incremental algorithm for maintaining DFS tree for undirected graphs. Zbl 1370.68227 Baswana, Surender; Khan, Shahbaz 6 2014 Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs. Zbl 1264.68068 Baswana, Surender; Khanna, Neelesh 10 2013 Fully dynamic randomized algorithms for graph spanners. Zbl 1295.05221 Baswana, Surender; Khurana, Sumeet; Sarkar, Soumojit 16 2012 Maintaining approximate maximum weighted matching in fully dynamic graphs. Zbl 1354.68289 Anand, Abhash; Baswana, Surender; Gupta, Manoj; Sen, Sandeep 6 2012 Single source distance oracle for planar digraphs avoiding a failed node or link. Zbl 1422.68044 Baswana, Surender; Lath, Utkarsh; Mehta, Anuradha S. 4 2012 Fully dynamic maximal matching in \(O(\log n)\) update time. Zbl 1292.68039 Baswana, Surender; Gupta, Manoj; Sen, Sandeep 14 2011 Additive spanners and \(({\alpha}, {\beta})\)-spanners. Zbl 1295.05094 Baswana, Surender; Kavitha, Telikepalli; Mehlhorn, Kurt; Pettie, Seth 32 2010 Faster algorithms for all-pairs approximate shortest paths in undirected graphs. Zbl 1227.05231 Baswana, Surender; Kavitha, Telikepalli 11 2010 Approximate shortest paths avoiding a failed vertex: optimal size data structures for unweighted graphs. Zbl 1230.68063 Khanna, Neelesh; Baswana, Surender 9 2010 Computing single source shortest paths using single-objective fitness. Zbl 1369.68296 Baswana, Surender; Biswas, Somenath; Doerr, Benjamin; Friedrich, Tobias; Kurur, Piyush P.; Neumann, Frank 13 2009 All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time. Zbl 1161.68036 Baswana, Surender; Goyal, Vishrut; Sen, Sandeep 1 2009 Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error. Zbl 1153.68405 Baswana, Surender; Gaur, Akshay; Sen, Sandeep; Upadhyay, Jayant 101 2008 Streaming algorithm for graph spanners-single pass and constant processing time per edge. Zbl 1186.68590 Baswana, Surender 11 2008 Fully dynamic algorithm for graph spanners with polylogarithmic update time. Zbl 1192.05150 Baswana, Surender; Sarkar, Soumojit 3 2008 A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Zbl 1118.68582 Baswana, Surender; Sen, Sandeep 34 2007 Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. Zbl 1120.68114 Baswana, Surender; Hariharan, Ramesh; Sen, Sandeep 11 2007 Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time. Zbl 1321.68214 Baswana, Surender; Sen, Sandeep 25 2006 Dynamic algorithms for graph spanners. Zbl 1131.68479 Baswana, Surender 7 2006 New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners. Zbl 1297.05066 Baswana, Surender; Kavitha, Telikepalli; Mehlhorn, Kurt; Pettie, Seth 14 2005 All-pairs nearly 2-approximate shortest-paths in \(O(n^2\text{ polylog }n)\) time. Zbl 1118.05311 Baswana, Surender; Goyal, Vishrut; Sen, Sandeep 7 2005 Approximate distance oracles for unweighted graphs in \(\tilde{\mathcal O}(n^2)\) time. Zbl 1317.68062 Baswana, Surender; Sen, Sandeep 7 2004 A simple linear time algorithm for computing a \((2k-1)\)-spanner of \(O(n^{1+1/k})\) size in weighted graphs. Zbl 1039.05056 Baswana, Surender; Sen, Sandeep 19 2003 Maintaining all-pairs approximate shortest path under deletion of edges. Zbl 1094.68603 Baswana, Surender; Hariharan, Ramesh; Sen, Sandeep 2 2003 Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. Zbl 1192.68469 Baswana, Surender; Hariharan, Ramesh; Sen, Sandeep 2 2002 Planar graph blocking for external searching. Zbl 1016.68032 Baswana, Surender; Sen, Sandeep 1 2002 all cited Publications top 5 cited Publications all top 5 Cited by 460 Authors 16 Baswana, Surender 15 Rauch Henzinger, Monika 11 Italiano, Giuseppe Francesco 10 Roditty, Liam 8 Bhattacharya, Sayan 7 Censor-Hillel, Keren 7 Elkin, Michael 7 Kavitha, Telikepalli 6 Peleg, David 6 Sudholt, Dirk 5 Choudhary, Keerti 5 Filtser, Arnold 5 Gavoille, Cyril 5 Gupta, Manoj Kumar 5 Mozes, Shay 5 Nanongkai, Danupon 5 Neiman, Ofer 5 Parter, Merav 5 Pettie, Seth 5 Sadakane, Kunihiko 5 Sen, Sandeep 5 Solomon, Shay 5 Vassilevska Williams, Virginia 5 Weimann, Oren 4 Ausiello, Giorgio 4 Barenboim, Leonid 4 Bernstein, Aaron 4 Bilò, Davide 4 Bodwin, Greg 4 Charalampopoulos, Panagiotis 4 Chechik, Shiri 4 Franciosa, Paolo Giulio 4 Karczmarz, Adam 4 Kawarabayashi, Ken-ichi 4 Khan, Shahbaz 4 Lenzen, Christoph 4 Leucci, Stefano 4 Proietti, Guido 3 Ahmed, Reyan 3 Alstrup, Stephen 3 Cohen, Sarel 3 Doerr, Benjamin 3 Dragan, Feodor F. 3 Gawrychowski, Paweł 3 Georgiadis, Loukas 3 Gómez, Renzo 3 Gualà, Luciano 3 Gupta, Shiv K. 3 Hamm, Keaton 3 Hon, Wing-Kai 3 Kobourov, Stephen G. 3 Krinninger, Sebastian 3 Łącki, Jakub 3 Lam, Kam-Yiu 3 Leniowski, Dariusz 3 Liao, Chung-Shou 3 Lovett, Shachar 3 Meka, Raghu 3 Miyazawa, Flavio Keidi 3 Nakamura, Kengo 3 Paz, Ami 3 Ribichini, Andrea 3 Spence, Richard 3 Thorup, Mikkel 3 Tóth, Csaba D. 3 Wakabayashi, Yoshiko 3 Wulff-Nilsen, Christian 3 Zhu, Chun Jiang 3 Zwick, Uri 2 Abboud, Amir 2 Abraham, Ittai 2 Aggarwal, Divesh 2 Ambainis, Andris 2 Andoni, Alexandr 2 Bačkurs, Artūrs 2 Bansal, Nikhil 2 Bar-Natan, Aviv 2 Barak, Boaz 2 Bartal, Yair 2 Braverman, Mark 2 Chen, Xi 2 Cohen, Michael B. 2 Czumaj, Artur 2 Dahlgaard, Søren 2 Däubel, Karl 2 Derbel, Bilel 2 Disser, Yann 2 Dolev, Danny 2 Dory, Michal 2 Duan, Ran 2 Ducoffe, Guillaume 2 Dumitrescu, Adrian 2 Feldman, Vitaly 2 Forster, Sebastian 2 Garg, Sanjam 2 Ghaffari, Mohsen 2 Ghosh, Anirban 2 Gupta, Anupam 2 Haeupler, Bernhard 2 Hardt, Moritz ...and 360 more Authors all top 5 Cited in 25 Serials 31 Algorithmica 23 Theoretical Computer Science 19 SIAM Journal on Computing 12 Distributed Computing 8 Information Processing Letters 6 SIAM Journal on Discrete Mathematics 4 Theory of Computing Systems 2 Artificial Intelligence 2 Journal of Computer and System Sciences 2 Information and Computation 2 Computational Geometry 1 ACM Computing Surveys 1 Networks 1 Computers & Operations Research 1 Random Structures & Algorithms 1 International Journal of Computational Geometry & Applications 1 The Electronic Journal of Combinatorics 1 Soft Computing 1 Journal of Combinatorial Optimization 1 Journal of the ACM 1 ACM Journal of Experimental Algorithmics 1 Journal of Discrete Algorithms 1 Discrete Mathematics, Algorithms and Applications 1 Algorithms 1 Computer Science Review all top 5 Cited in 14 Fields 262 Computer science (68-XX) 122 Combinatorics (05-XX) 32 Operations research, mathematical programming (90-XX) 20 Information and communication theory, circuits (94-XX) 9 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 8 Numerical analysis (65-XX) 3 Quantum theory (81-XX) 2 Group theory and generalizations (20-XX) 2 Statistics (62-XX) 1 Mathematical logic and foundations (03-XX) 1 Number theory (11-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Probability theory and stochastic processes (60-XX) 1 Statistical mechanics, structure of matter (82-XX) Citations by Year