咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >FULLY DYNAMIC ALGORITHMS FOR 2... 收藏

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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分