版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.