×
Author ID: baswana.surender Recent zbMATH articles by "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

Publications by Year

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

Citations by Year