[{"language":[{"iso":"eng"}],"status":"public","publication_identifier":{"isbn":["978-3-540-61155-4"],"issn":["0302-9743"]},"editor":[{"full_name":"Alur, Rajeev","last_name":"Alur","first_name":"Rajeev"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"last_name":"Sontag","first_name":"Eduardo D","full_name":"Sontag, Eduardo D"}],"intvolume":"      1066","page":"IX, 619","volume":1066,"alternative_title":["LNCS"],"quality_controlled":"1","type":"book_editor","series_title":"Lecture Notes in Computer Science","_id":"4612","date_published":"1996-01-01T00:00:00Z","doi":"10.1007/BFb0020931","citation":{"ama":"Alur R, Henzinger TA, Sontag ED, eds. <i>Hybrid Systems III: Verification and Control</i>. Vol 1066. Berlin ; Heidelberg: Springer; 1996. doi:<a href=\"https://doi.org/10.1007/BFb0020931\">10.1007/BFb0020931</a>","ieee":"R. Alur, T. A. Henzinger, and E. D. Sontag, Eds., <i>Hybrid Systems III: Verification and Control</i>, vol. 1066. Berlin ; Heidelberg: Springer, 1996.","mla":"Alur, Rajeev, et al., editors. <i>Hybrid Systems III: Verification and Control</i>. Vol. 1066, Springer, 1996, doi:<a href=\"https://doi.org/10.1007/BFb0020931\">10.1007/BFb0020931</a>.","apa":"Alur, R., Henzinger, T. A., &#38; Sontag, E. D. (Eds.). (1996). <i>Hybrid Systems III: Verification and Control</i> (Vol. 1066). Berlin ; Heidelberg: Springer. <a href=\"https://doi.org/10.1007/BFb0020931\">https://doi.org/10.1007/BFb0020931</a>","chicago":"Alur, Rajeev, Thomas A Henzinger, and Eduardo D Sontag, eds. <i>Hybrid Systems III: Verification and Control</i>. Vol. 1066. Lecture Notes in Computer Science. Berlin ; Heidelberg: Springer, 1996. <a href=\"https://doi.org/10.1007/BFb0020931\">https://doi.org/10.1007/BFb0020931</a>.","short":"R. Alur, T.A. Henzinger, E.D. Sontag, eds., Hybrid Systems III: Verification and Control, Springer, Berlin ; Heidelberg, 1996.","ista":"Alur R, Henzinger TA, Sontag ED eds. 1996. Hybrid Systems III: Verification and Control, Berlin ; Heidelberg: Springer, IX, 619p."},"article_processing_charge":"No","date_updated":"2021-12-22T13:57:33Z","date_created":"2018-12-11T12:09:45Z","place":"Berlin ; Heidelberg","publist_id":"97","publisher":"Springer","month":"01","oa_version":"None","title":"Hybrid Systems III: Verification and Control","extern":"1","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publication_status":"published","day":"01","year":"1996"},{"oa_version":"None","publisher":"Springer Nature","month":"09","title":"Certificates and fast algorithms for biconnectivity in fully-dynamic graphs","extern":"1","publication":"3rd Annual European Symposium on Algorithms","author":[{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"full_name":"Poutré, Han","last_name":"Poutré","first_name":"Han"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"end_date":"1995-09-27","start_date":"1995-09-25","location":"Corfu, Greece","name":"ESA: European Symposium on Algorithms"},"year":"1995","day":"01","date_published":"1995-09-01T00:00:00Z","_id":"11805","citation":{"ista":"Henzinger M, 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.","short":"M. Henzinger, H. Poutré, in:, 3rd Annual European Symposium on Algorithms, Springer Nature, 1995, pp. 171–184.","chicago":"Henzinger, Monika, 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>.","apa":"Henzinger, M., &#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>","ieee":"M. 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.","mla":"Henzinger, Monika, 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>.","ama":"Henzinger M, 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>"},"doi":"10.1007/3-540-60313-1_142","article_processing_charge":"No","date_updated":"2024-11-06T12:16:15Z","date_created":"2022-08-11T14:09:52Z","intvolume":"       979","volume":979,"page":"171–184","scopus_import":"1","alternative_title":["LNCS"],"quality_controlled":"1","type":"conference","status":"public","publication_identifier":{"eissn":["1611-3349"],"eisbn":["9783540449133"],"isbn":["9783540603139"],"issn":["0302-9743"]},"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","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]."}]},{"date_updated":"2024-11-06T08:23:27Z","date_created":"2022-08-11T14:17:33Z","article_processing_charge":"No","citation":{"short":"M. Henzinger, in:, 22nd International Colloquium on Automata, Languages and Programming, Springer Nature, 1995, pp. 280–291.","ista":"Henzinger M. 1995. Approximating minimum cuts under insertions. 22nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 944, 280–291.","mla":"Henzinger, Monika. “Approximating Minimum Cuts under Insertions.” <i>22nd International Colloquium on Automata, Languages and Programming</i>, vol. 944, Springer Nature, 1995, pp. 280–291, doi:<a href=\"https://doi.org/10.1007/3-540-60084-1_81\">10.1007/3-540-60084-1_81</a>.","ieee":"M. Henzinger, “Approximating minimum cuts under insertions,” in <i>22nd International Colloquium on Automata, Languages and Programming</i>, Szeged, Hungary, 1995, vol. 944, pp. 280–291.","ama":"Henzinger M. Approximating minimum cuts under insertions. In: <i>22nd International Colloquium on Automata, Languages and Programming</i>. Vol 944. Springer Nature; 1995:280–291. doi:<a href=\"https://doi.org/10.1007/3-540-60084-1_81\">10.1007/3-540-60084-1_81</a>","chicago":"Henzinger, Monika. “Approximating Minimum Cuts under Insertions.” In <i>22nd International Colloquium on Automata, Languages and Programming</i>, 944:280–291. Springer Nature, 1995. <a href=\"https://doi.org/10.1007/3-540-60084-1_81\">https://doi.org/10.1007/3-540-60084-1_81</a>.","apa":"Henzinger, M. (1995). Approximating minimum cuts under insertions. In <i>22nd International Colloquium on Automata, Languages and Programming</i> (Vol. 944, pp. 280–291). Szeged, Hungary: Springer Nature. <a href=\"https://doi.org/10.1007/3-540-60084-1_81\">https://doi.org/10.1007/3-540-60084-1_81</a>"},"doi":"10.1007/3-540-60084-1_81","date_published":"1995-07-01T00:00:00Z","_id":"11806","conference":{"start_date":"1995-07-10","end_date":"1995-07-14","name":"ICALP: International Colloquium on Automata, Languages, and Programming","location":"Szeged, Hungary"},"year":"1995","day":"01","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Approximating minimum cuts under insertions","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"}],"extern":"1","publication":"22nd International Colloquium on Automata, Languages and Programming","oa_version":"None","publisher":"Springer Nature","month":"07","abstract":[{"lang":"eng","text":"This paper presents insertions-only algorithms for maintaining the exact and approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact size k in time O(1) or O(log n) and a cut of size k in time linear in its size. The amortized time per insertion is O(1/ε 2) for a (2+ε)-approximation, O((log λ)((log n)/ε)2) for a (1+ε)-approximation, and O(λ log n) for the exact size of the minimum edge cut, where n is the number of nodes in the graph, λ is the size of the minimum cut and ε>0. The (2+ε)-approximation algorithm and the exact algorithm are deterministic, the (1+ε)-approximation algorithm is randomized. The algorithms are optimal in the sense that the time needed for m insertions matches the time needed by the best static algorithm on a m-edge graph. We also present a static 2-approximation algorithm for the size κ of the minimum vertex cut in a graph, which takes time O(n 2 min(√n,κ)). This is a factor of κ faster than the best algorithm for computing the exact size, which takes time O(κ 2 n 2 +κ 3 n 1.5). We give an insertionsonly algorithm for maintaining a (2+ε)-approximation of the minimum vertex cut with amortized insertion time O(n(logκk)/ε)."}],"publication_identifier":{"issn":["0302-9743"],"isbn":["9783540494256"],"eisbn":["9783540600848"],"eissn":["1611-3349"]},"status":"public","language":[{"iso":"eng"}],"scopus_import":"1","alternative_title":["LNCS"],"type":"conference","quality_controlled":"1","volume":944,"page":"280–291","intvolume":"       944"}]