FULLY DYNAMIC ALGORITHMS FOR 2-EDGE CONNECTIVITY

作     者：GALIL, Z ITALIANO, GF 

作者机构：UNIV ROME I-00100 ROME ITALY IBM CORP THOMAS J WATSON RES CTR YORKTOWN HTS NY 10598 USA TEL AVIV UNIV IL-69978 TEL AVIV ISRAEL 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1992年第21卷第6期

页      面：1047-1069页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：ANALYSIS OF ALGORITHMS DYNAMIC DATA STRUCTURES EDGE CONNECTIVITY VERTEX CONNECTIVITY 

摘      要：This paper studies the problem of maintaining the 2-edge-connected components of a graph undergoing repeated dynamic modifications, such as edge insertions and edge deletions. It is shown how to test at any time whether two vertices belong to the same 2-edge-connected component, and how to insert and delete an edge in O(m2/3) time in the worst case, where m is the current number of edges in the graph. This answers a question posed by Westbrook and Tarjan [Tech. Report CS-TR-229-89, Dept. of Computer Science, Princeton University, Princeton, NJ, August 1989;Algorithmica, to appear]. For planar graphs, the paper presents algorithms that support all these operations in O(square-root n log log n) worst-case time each, where n is the total number of vertices in the graph.