[{"publication":"Algorithmica","citation":{"ama":"Henzinger MH. Fully dynamic biconnectivity in graphs. Algorithmica. 1995;13(6):503-538. doi:10.1007/bf01189067","apa":"Henzinger, M. H. (1995). Fully dynamic biconnectivity in graphs. Algorithmica. Springer Nature. https://doi.org/10.1007/bf01189067","ieee":"M. H. Henzinger, “Fully dynamic biconnectivity in graphs,” Algorithmica, vol. 13, no. 6. Springer Nature, pp. 503–538, 1995.","ista":"Henzinger MH. 1995. Fully dynamic biconnectivity in graphs. Algorithmica. 13(6), 503–538.","short":"M.H. Henzinger, Algorithmica 13 (1995) 503–538.","mla":"Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica, vol. 13, no. 6, Springer Nature, 1995, pp. 503–38, doi:10.1007/bf01189067.","chicago":"Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica. Springer Nature, 1995. https://doi.org/10.1007/bf01189067."},"article_type":"original","quality_controlled":"1","page":"503-538","doi":"10.1007/bf01189067","date_published":"1995-06-01T00:00:00Z","language":[{"iso":"eng"}],"scopus_import":"1","month":"06","day":"01","article_processing_charge":"No","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11677","year":"1995","status":"public","publication_status":"published","title":"Fully dynamic biconnectivity in graphs","publisher":"Springer Nature","intvolume":" 13","author":[{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H"}],"date_updated":"2022-09-12T09:00:14Z","date_created":"2022-07-27T14:50:46Z","volume":13,"oa_version":"None","type":"journal_article","abstract":[{"lang":"eng","text":"We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m 2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently.\r\n\r\nIf the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log2 n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n 2/3 ) per update or query."}],"issue":"6","extern":"1"},{"publication":"Proceedings of IEEE 36th Annual Foundations of Computer Science","citation":{"ama":"Henzinger MH, King V. Fully dynamic biconnectivity and transitive closure. In: Proceedings of IEEE 36th Annual Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 1995:664-672. doi:10.1109/SFCS.1995.492668","ista":"Henzinger MH, King V. 1995. Fully dynamic biconnectivity and transitive closure. Proceedings of IEEE 36th Annual Foundations of Computer Science. Foundations of Computer Science, 664–672.","apa":"Henzinger, M. H., & King, V. (1995). Fully dynamic biconnectivity and transitive closure. In Proceedings of IEEE 36th Annual Foundations of Computer Science (pp. 664–672). Milwaukee, WI, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/SFCS.1995.492668","ieee":"M. H. Henzinger and V. King, “Fully dynamic biconnectivity and transitive closure,” in Proceedings of IEEE 36th Annual Foundations of Computer Science, Milwaukee, WI, United States, 1995, pp. 664–672.","mla":"Henzinger, Monika H., and V. King. “Fully Dynamic Biconnectivity and Transitive Closure.” Proceedings of IEEE 36th Annual Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 1995, pp. 664–72, doi:10.1109/SFCS.1995.492668.","short":"M.H. Henzinger, V. King, in:, Proceedings of IEEE 36th Annual Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 1995, pp. 664–672.","chicago":"Henzinger, Monika H, and V. King. “Fully Dynamic Biconnectivity and Transitive Closure.” In Proceedings of IEEE 36th Annual Foundations of Computer Science, 664–72. Institute of Electrical and Electronics Engineers, 1995. https://doi.org/10.1109/SFCS.1995.492668."},"quality_controlled":"1","page":"664-672","conference":{"end_date":"1995-10-25","location":"Milwaukee, WI, United States","start_date":"1995-10-23","name":"Foundations of Computer Science"},"date_published":"1995-11-01T00:00:00Z","doi":"10.1109/SFCS.1995.492668","language":[{"iso":"eng"}],"scopus_import":"1","month":"11","day":"01","article_processing_charge":"No","publication_identifier":{"issn":["0272-5428"],"isbn":["0-8186-7183-1"]},"_id":"11684","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"1995","publication_status":"published","status":"public","title":"Fully dynamic biconnectivity and transitive closure","publisher":"Institute of Electrical and Electronics Engineers","author":[{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"V.","last_name":"King","full_name":"King, V."}],"date_created":"2022-07-28T11:28:13Z","date_updated":"2023-02-09T11:35:17Z","oa_version":"None","type":"conference","abstract":[{"text":"This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(log/sup 2/n) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized algorithm with the update time amortized update time O(log/sup 4/n). Only recently the best deterministic result for this problem was improved to O(/spl radic/nlog/sup 2/n). We also give the first fully dynamic and a novel deletions-only transitive closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo algorithms. Let n be the number of nodes in the graph and let m/spl circ/ be the average number of edges in the graph during the whole update sequence: The fully dynamic algorithms achieve (1) query time O(n/logn) and update time O(m/spl circ//spl radic/nlog/sup 2/n+n); or (2) query time O(n/logn) and update time O(nm/spl circ//sup /spl mu/-1/)log/sup 2/n=O(nm/spl circ//sup 0.58/log/sup 2/n), where /spl mu/ is the exponent for boolean matrix multiplication (currently /spl mu/=2.38). The deletions-only algorithm answers queries in time O(n/logn). Its amortized update time is O(nlog/sup 2/n).","lang":"eng"}],"extern":"1"},{"volume":944,"oa_version":"None","date_created":"2022-08-11T14:17:33Z","date_updated":"2023-02-14T08:09:08Z","author":[{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"}],"publisher":"Springer Nature","intvolume":" 944","publication_status":"published","status":"public","title":"Approximating minimum cuts under insertions","_id":"11806","year":"1995","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","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)/ε)."}],"alternative_title":["LNCS"],"type":"conference","language":[{"iso":"eng"}],"date_published":"1995-07-01T00:00:00Z","doi":"10.1007/3-540-60084-1_81","conference":{"name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"1995-07-10","location":"Szeged, Hungary","end_date":"1995-07-14"},"page":"280–291","quality_controlled":"1","citation":{"ama":"Henzinger MH. Approximating minimum cuts under insertions. In: 22nd International Colloquium on Automata, Languages and Programming. Vol 944. Springer Nature; 1995:280–291. doi:10.1007/3-540-60084-1_81","ista":"Henzinger MH. 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.","ieee":"M. H. Henzinger, “Approximating minimum cuts under insertions,” in 22nd International Colloquium on Automata, Languages and Programming, Szeged, Hungary, 1995, vol. 944, pp. 280–291.","apa":"Henzinger, M. H. (1995). Approximating minimum cuts under insertions. In 22nd International Colloquium on Automata, Languages and Programming (Vol. 944, pp. 280–291). Szeged, Hungary: Springer Nature. https://doi.org/10.1007/3-540-60084-1_81","mla":"Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.” 22nd International Colloquium on Automata, Languages and Programming, vol. 944, Springer Nature, 1995, pp. 280–291, doi:10.1007/3-540-60084-1_81.","short":"M.H. Henzinger, in:, 22nd International Colloquium on Automata, Languages and Programming, Springer Nature, 1995, pp. 280–291.","chicago":"Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.” In 22nd International Colloquium on Automata, Languages and Programming, 944:280–291. Springer Nature, 1995. https://doi.org/10.1007/3-540-60084-1_81."},"publication":"22nd International Colloquium on Automata, Languages and Programming","publication_identifier":{"eisbn":["9783540600848"],"issn":["0302-9743"],"isbn":["9783540494256"],"eissn":["1611-3349"]},"article_processing_charge":"No","day":"01","month":"07","scopus_import":"1"},{"scopus_import":"1","month":"09","day":"01","article_processing_charge":"No","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783540603139"],"eisbn":["9783540449133"],"issn":["0302-9743"]},"publication":"3rd Annual European Symposium on Algorithms","citation":{"mla":"Henzinger, Monika H., and Han Poutré. “Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs.” 3rd Annual European Symposium on Algorithms, vol. 979, Springer Nature, 1995, pp. 171–184, doi:10.1007/3-540-60313-1_142.","short":"M.H. Henzinger, H. Poutré, in:, 3rd Annual European Symposium on Algorithms, Springer Nature, 1995, pp. 171–184.","chicago":"Henzinger, Monika H, and Han Poutré. “Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs.” In 3rd Annual European Symposium on Algorithms, 979:171–184. Springer Nature, 1995. https://doi.org/10.1007/3-540-60313-1_142.","ama":"Henzinger MH, Poutré H. Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In: 3rd Annual European Symposium on Algorithms. Vol 979. Springer Nature; 1995:171–184. doi:10.1007/3-540-60313-1_142","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.","ieee":"M. H. Henzinger and H. Poutré, “Certificates and fast algorithms for biconnectivity in fully-dynamic graphs,” in 3rd Annual European Symposium on Algorithms, Corfu, Greece, 1995, vol. 979, pp. 171–184.","apa":"Henzinger, M. H., & Poutré, H. (1995). Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In 3rd Annual European Symposium on Algorithms (Vol. 979, pp. 171–184). Corfu, Greece: Springer Nature. https://doi.org/10.1007/3-540-60313-1_142"},"quality_controlled":"1","page":"171–184","conference":{"name":"ESA: European Symposium on Algorithms","start_date":"1995-09-25","location":"Corfu, Greece","end_date":"1995-09-27"},"date_published":"1995-09-01T00:00:00Z","doi":"10.1007/3-540-60313-1_142","language":[{"iso":"eng"}],"type":"conference","alternative_title":["LNCS"],"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]."}],"extern":"1","_id":"11805","year":"1995","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Certificates and fast algorithms for biconnectivity in fully-dynamic graphs","publication_status":"published","publisher":"Springer Nature","intvolume":" 979","author":[{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"last_name":"Poutré","first_name":"Han","full_name":"Poutré, Han"}],"date_created":"2022-08-11T14:09:52Z","date_updated":"2023-02-14T08:02:03Z","volume":979,"oa_version":"None"},{"type":"conference","extern":"1","abstract":[{"text":"We present a model with restricted randomness for edge updates in dynamic graph algorithms and a general technique\r\nfor analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1) it allows restrictions on the set of edges which can be used for insertions and (2) the type (insertion or deletion) of each update operation is arbitrary, i.e., not random. We use our technique to analyze existing and new dynamic algorithms for maximum cardinality matching, minimum spanning forest, connectivity, 2-edge connectivity,\r\nk-edge connectivity, k-vertex connectivity, and bipartiteness. Given a random graph G with mo edges and n vertices and\r\na sequence of 1 update operations such that the graph contains rni edges after operation i, the expected time for performing the updates for any 1 is O(1 logn + n xi=, l/fii) in the case of minimum spanning forests, connectivity, 2-\r\nedge connectivity, and bipartiteness. The expected time per update operation is O(n) in the case of maximum matching. For k-edge and k-vertex connectivity we also give improved bounds. Additionally we give an insertions-only algorithm for maximum cardinality matching with worst-case O(n) amortized time per insertion. ","lang":"eng"}],"publisher":"Society for Industrial and Applied Mathematics","title":"Average case analysis of dynamic graph algorithms","publication_status":"published","status":"public","_id":"11928","year":"1995","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","date_updated":"2023-02-21T16:24:58Z","date_created":"2022-08-19T07:10:23Z","related_material":{"record":[{"id":"11680","relation":"later_version","status":"public"}]},"author":[{"full_name":"Alberts, David","last_name":"Alberts","first_name":"David"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H"}],"scopus_import":"1","publication_identifier":{"isbn":["0898713498"]},"article_processing_charge":"No","month":"01","day":"01","page":"312-321","quality_controlled":"1","citation":{"short":"D. Alberts, M.H. Henzinger, in:, 6th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 1995, pp. 312–321.","mla":"Alberts, David, and Monika H. Henzinger. “Average Case Analysis of Dynamic Graph Algorithms.” 6th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 1995, pp. 312–21.","chicago":"Alberts, David, and Monika H Henzinger. “Average Case Analysis of Dynamic Graph Algorithms.” In 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 312–21. Society for Industrial and Applied Mathematics, 1995.","ama":"Alberts D, Henzinger MH. Average case analysis of dynamic graph algorithms. In: 6th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 1995:312-321.","ieee":"D. Alberts and M. H. Henzinger, “Average case analysis of dynamic graph algorithms,” in 6th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, United States, 1995, pp. 312–321.","apa":"Alberts, D., & Henzinger, M. H. (1995). Average case analysis of dynamic graph algorithms. In 6th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 312–321). San Francisco, CA, United States: Society for Industrial and Applied Mathematics.","ista":"Alberts D, Henzinger MH. 1995. Average case analysis of dynamic graph algorithms. 6th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 312–321."},"main_file_link":[{"url":"https://dl.acm.org/doi/10.5555/313651.313712","open_access":"1"}],"oa":1,"publication":"6th Annual ACM-SIAM Symposium on Discrete Algorithms","language":[{"iso":"eng"}],"date_published":"1995-01-01T00:00:00Z","conference":{"end_date":"1995-01-24","start_date":"1995-01-22","location":"San Francisco, CA, United States","name":"SODA: Symposium on Discrete Algorithms"}}]