--- _id: '11677' 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." article_processing_charge: No article_type: original author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 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 chicago: Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica. Springer Nature, 1995. 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. mla: Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica, vol. 13, no. 6, Springer Nature, 1995, pp. 503–38, doi:10.1007/bf01189067. short: M.H. Henzinger, Algorithmica 13 (1995) 503–538. date_created: 2022-07-27T14:50:46Z date_published: 1995-06-01T00:00:00Z date_updated: 2022-09-12T09:00:14Z day: '01' doi: 10.1007/bf01189067 extern: '1' intvolume: ' 13' issue: '6' language: - iso: eng month: '06' oa_version: None page: 503-538 publication: Algorithmica publication_identifier: eissn: - 1432-0541 issn: - 0178-4617 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Fully dynamic biconnectivity in graphs type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 13 year: '1995' ... --- _id: '11684' abstract: - lang: eng 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).' article_processing_charge: No author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: V. full_name: King, V. last_name: King 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' 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' 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. 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. 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. 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. conference: end_date: 1995-10-25 location: Milwaukee, WI, United States name: Foundations of Computer Science start_date: 1995-10-23 date_created: 2022-07-28T11:28:13Z date_published: 1995-11-01T00:00:00Z date_updated: 2023-02-09T11:35:17Z day: '01' doi: 10.1109/SFCS.1995.492668 extern: '1' language: - iso: eng month: '11' oa_version: None page: 664-672 publication: Proceedings of IEEE 36th Annual Foundations of Computer Science publication_identifier: isbn: - 0-8186-7183-1 issn: - 0272-5428 publication_status: published publisher: Institute of Electrical and Electronics Engineers quality_controlled: '1' scopus_import: '1' status: public title: Fully dynamic biconnectivity and transitive closure type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '1995' ... --- _id: '11806' 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 article_processing_charge: No author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 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' 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' 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. 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. 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.' 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. conference: end_date: 1995-07-14 location: Szeged, Hungary name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 1995-07-10 date_created: 2022-08-11T14:17:33Z date_published: 1995-07-01T00:00:00Z date_updated: 2023-02-14T08:09:08Z day: '01' doi: 10.1007/3-540-60084-1_81 extern: '1' intvolume: ' 944' language: - iso: eng month: '07' oa_version: None page: 280–291 publication: 22nd International Colloquium on Automata, Languages and Programming publication_identifier: eisbn: - '9783540600848' eissn: - 1611-3349 isbn: - '9783540494256' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Approximating minimum cuts under insertions type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 944 year: '1995' ... --- _id: '11805' 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]. alternative_title: - LNCS article_processing_charge: No author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Han full_name: Poutré, Han last_name: Poutré citation: 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' 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' 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. 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. 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.' 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. conference: end_date: 1995-09-27 location: Corfu, Greece name: 'ESA: European Symposium on Algorithms' start_date: 1995-09-25 date_created: 2022-08-11T14:09:52Z date_published: 1995-09-01T00:00:00Z date_updated: 2023-02-14T08:02:03Z day: '01' doi: 10.1007/3-540-60313-1_142 extern: '1' intvolume: ' 979' language: - iso: eng month: '09' oa_version: None page: 171–184 publication: 3rd Annual European Symposium on Algorithms publication_identifier: eisbn: - '9783540449133' eissn: - 1611-3349 isbn: - '9783540603139' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Certificates and fast algorithms for biconnectivity in fully-dynamic graphs type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 979 year: '1995' ... --- _id: '11928' abstract: - lang: eng 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. " article_processing_charge: No author: - first_name: David full_name: Alberts, David last_name: Alberts - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 citation: 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.' 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.' 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. 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. 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.' 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. 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. conference: end_date: 1995-01-24 location: San Francisco, CA, United States name: 'SODA: Symposium on Discrete Algorithms' start_date: 1995-01-22 date_created: 2022-08-19T07:10:23Z date_published: 1995-01-01T00:00:00Z date_updated: 2023-02-21T16:24:58Z day: '01' extern: '1' language: - iso: eng main_file_link: - open_access: '1' url: https://dl.acm.org/doi/10.5555/313651.313712 month: '01' oa: 1 oa_version: Published Version page: 312-321 publication: 6th Annual ACM-SIAM Symposium on Discrete Algorithms publication_identifier: isbn: - '0898713498' publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' related_material: record: - id: '11680' relation: later_version status: public scopus_import: '1' status: public title: Average case analysis of dynamic graph algorithms type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '1995' ...