[{"scopus_import":"1","publication":"3rd Annual European Symposium on Algorithms","_id":"11805","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"Poutré, Han","first_name":"Han","last_name":"Poutré"}],"date_created":"2022-08-11T14:09:52Z","article_processing_charge":"No","oa_version":"None","publication_status":"published","intvolume":"       979","alternative_title":["LNCS"],"title":"Certificates and fast algorithms for biconnectivity in fully-dynamic graphs","month":"09","quality_controlled":"1","page":"171–184","language":[{"iso":"eng"}],"publisher":"Springer Nature","conference":{"name":"ESA: European Symposium on Algorithms","start_date":"1995-09-25","end_date":"1995-09-27","location":"Corfu, Greece"},"citation":{"mla":"Henzinger, Monika H., and Han Poutré. “Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs.” <i>3rd Annual European Symposium on Algorithms</i>, vol. 979, Springer Nature, 1995, pp. 171–184, doi:<a href=\"https://doi.org/10.1007/3-540-60313-1_142\">10.1007/3-540-60313-1_142</a>.","short":"M.H. Henzinger, H. Poutré, in:, 3rd Annual European Symposium on Algorithms, Springer Nature, 1995, pp. 171–184.","ista":"Henzinger MH, Poutré H. 1995. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. 3rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 979, 171–184.","apa":"Henzinger, M. H., &#38; Poutré, H. (1995). Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In <i>3rd Annual European Symposium on Algorithms</i> (Vol. 979, pp. 171–184). Corfu, Greece: Springer Nature. <a href=\"https://doi.org/10.1007/3-540-60313-1_142\">https://doi.org/10.1007/3-540-60313-1_142</a>","ama":"Henzinger MH, Poutré H. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In: <i>3rd Annual European Symposium on Algorithms</i>. Vol 979. Springer Nature; 1995:171–184. doi:<a href=\"https://doi.org/10.1007/3-540-60313-1_142\">10.1007/3-540-60313-1_142</a>","chicago":"Henzinger, Monika H, and Han Poutré. “Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs.” In <i>3rd Annual European Symposium on Algorithms</i>, 979:171–184. Springer Nature, 1995. <a href=\"https://doi.org/10.1007/3-540-60313-1_142\">https://doi.org/10.1007/3-540-60313-1_142</a>.","ieee":"M. H. Henzinger and H. Poutré, “Certificates and fast algorithms for biconnectivity in fully-dynamic graphs,” in <i>3rd Annual European Symposium on Algorithms</i>, Corfu, Greece, 1995, vol. 979, pp. 171–184."},"year":"1995","date_updated":"2023-02-14T08:02:03Z","type":"conference","date_published":"1995-09-01T00:00:00Z","day":"01","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783540449133"],"isbn":["9783540603139"]},"doi":"10.1007/3-540-60313-1_142","abstract":[{"text":"In this paper, we present sparse certificates for biconnectivity together with algorithms for updating these certificates. We thus obtain fully-dynamic algorithms for biconnectivity in graphs that run in O(√n log n log⌈m/n⌉) amortized time per operation, where m is the number of edges and n is the number of nodes in the graph. This improves upon the results in [11], in which algorithms were presented running in O(√m) amortized time, and solves the open problem to find certificates to speed up biconnectivity, as stated in [2].","lang":"eng"}],"volume":979,"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1"}]