Fetching the paper…
Reading the bibliography…
We give offline algorithms for processing a sequence of $2$ and $3$ edge and vertex connectivity queries in a fully-dynamic undirected graph.
Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2
1973
Earlier work this paper cites.
Bienstock, D., Monma, C.L.: On the complexity of covering vertices by faces in a planar graph. SIAM J. Comput. 17
1988
Earlier work this paper cites.
Di Battista, G., Tamassia, R.: On-line graph algorithms with spqr-trees. In: Proceedings of the seventeenth international colloquium on Automata, languages and programming. pp. 598–611. New York, NY, USA (1990)
1990
Earlier work this paper cites.
Westbrook, J., Tarjan, R.: Maintaining bridge-connected and biconnected components on-line. Algorithmica 7
1992
Earlier work this paper cites.
Eppstein, D.: Offline algorithms for dynamic minimum spanning tree problems. J. Algorithms 17
1994
Earlier work this paper cites.
Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification–a technique for speeding up dynamic graph algorithms. J. ACM 44
1997
Earlier work this paper cites.
Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing. pp. 79–89. STOC ’98, ACM, New York, NY, USA (1998)
1998
Earlier work this paper cites.
Karger, D.R.: Minimum cuts in near-linear time. J. ACM 47
2000
Earlier work this paper cites.
Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proceedings of the thirty-second annual ACM symposium on Theory of computing. pp. 343–350. STOC ’00, ACM, New York, NY, USA (2000)
2000
Earlier work this paper cites.
Weiskircher, R.: New Applications of SPQR-Trees in Graph Drawing. Ph.D. thesis, Universität des Saarlandes (2002)
2002
Earlier work this paper cites.
Patracscu, M., Demaine, E.D.: Lower bounds for dynamic connectivity. In: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. pp. 546–553. STOC ’04, ACM, New York, NY, USA (2004)
2004
Earlier work this paper cites.
Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T.H.: Separator-based sparsification ii: edge and vertex connectivity. In: Siam Journal on Computing (2006)
2006
Earlier work this paper cites.
Tsin, Y.H.: Yet another optimal algorithm for 3-edge-connectivity. Journal of Discrete Algorithms 7
2009
Earlier work this paper cites.
Kratsch, S., Wahlstrom, M.: Representative sets and irrelevant vertices: New tools for kernelization. In: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. pp. 450–459. FOCS ’12 (2012)
2012
Cited alongside, same era.
Kapron, B., King, V., Mountjoy, B.: Dynamic graph connectivity in polylogarithmic worst case time. SODA (2013)
2013
Cited alongside, same era.
Lacki, J., Sankowski, P.: Reachability in graph timelines. ITCS (2013)
2013
Cited alongside, same era.
Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. pp. 434–443. FOCS ’14 (2014)
2014
Cited alongside, same era.
Abboud, A., Williams, V.V., Yu, H.: Matching triangles and basing hardness on an extremely popular conjecture. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015. pp. 41–50 (2015)
Durfee, D., Kyng, R., Peebles, J., Rao, A.B., Sachdeva, S.: Sampling random spanning trees faster than matrix multiplication. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. pp. 730–742 (2017)
2017
Closest in time.
Goranci, G., Henzinger, M., Peng, P.: The power of vertex sparsifiers in dynamic graph algorithms. In: European Symposium on Algorithms (ESA). pp. 45:1–45:14 (2017)
2017
Closest in time.
Huang, S.E., Huang, D., Kopelowitz, T., Pettie, S.: Fully dynamic connectivity in O ( log n ( log log n ) 2 ) O(\log n(\log\log n)^{2}) amortized expected time. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 510–520 (2017)
2017
Closest in time.
Peng, R., Sandlund, B., Sleator, D.D.: Offline dynamic higher connectivity. CoRR abs/1708.03812
2017
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2015
Cited alongside, same era.
Assadi, S., Khanna, S., Li, Y., Tannen, V.: Dynamic sketching for graph optimization problems with applications to cut-preserving sketches. In: FSTTCS (2015)
2015
Cited alongside, same era.
Holm, J., Rotenberg, E., Wulff-Nilsen, C.: Faster fully-dynamic minimum spanning forest. In: Bansal, N., Finocchi, I. (eds.) Algorithms - ESA 2015. pp. 742–753. Springer Berlin Heidelberg, Berlin, Heidelberg (2015)
2015
Cited alongside, same era.
Karczmarz, A., Lacki, J.: Fast and simple connectivity in graph timelines. In: Dehne, F., Sack, J.R., Stege, U. (eds.) Algorithms and Data Structures: 14th International Symposium, WADS 2015. pp. 458–469 (2015)
2015
Cited alongside, same era.
Abboud, A., Dahlgaard, S.: Popular conjectures as a barrier for dynamic planar graph algorithms. In: IEEE 57th Annual Symposium on Foundations of Computer Science. pp. 477–486 (10 2016)
2016
Cited alongside, same era.
Abraham, I., Durfee, D., Koutis, I., Krinninger, S., Peng, R.: On fully dynamic graph sparsifiers. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 335–344 (Oct 2016)
2016
Cited alongside, same era.
Dahlgaard, S.: On the hardness of partially dynamic graph problems and connections to diameter. In: 43rd International Colloquium on Automata, Languages, and Programming (2016)
2016
Cited alongside, same era.
Fafianie, S., Hols, E.M.C., Kratsch, S., Quyen, V.A.: Preprocessing under uncertainty: Matroid intersection. In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). vol. 58, pp. 35:1–35:14 (2016)
2016
Cited alongside, same era.
2017
Closest in time.
2018
Closest in time.
Goranci, G., Henzinger, M., Peng, P.: Dynamic effective resistances and approximate schur complement on separable graphs. In: 26th Annual European Symposium on Algorithms (ESA 2018). vol. 112, pp. 40:1–40:15 (2018)
2018
Closest in time.
Goranci, G., Henzinger, M., Saranurak, T.: Fast incremental algorithms via local sparsifiers. CoRR (2018), https://drive.google.com/file/d/1SJrbzuz_szMwsBfeBZfGUWkDEbZKAGD5/view
2018
Closest in time.
Holm, J., Rotenberg, E., Thorup, M.: Dynamic bridge-finding in O ~ ( log 2 n ) \tilde{O}(\log^{2}n) amortized time. In: Symposium on Discrete Algorithms (SODA) (2018)
2018
Closest in time.
2018
Closest in time.
Li, H., Zhang, Z.: Kirchhoff index as a measure of edge centrality in weighted networks: Nearly linear time algorithms. In: Symposium on Discrete Algorithms (SODA). pp. 2377–2396 (2018)
2018
Closest in time.
Durfee, D., Gao, Y., Goranci, G., Peng, R.: Fully dynamic spectral vertex sparsifiers and applications. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing. STOC ’19, ACM (2019)
2019
Closest in time.