文章基本信息

标题：Incremental 2-Edge-Connectivity in Directed Graphs
本地全文：下载
作者：Loukas Georgiadis ; Giuseppe F. Italiano ; Nikos Parotsidis 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：49:1-49:15
DOI：10.4230/LIPIcs.ICALP.2016.49
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We present an algorithm that can update the 2-edge-connected blocks of a directed graph with n vertices through a sequence of m edge insertions in a total of O(m*n) time. After each insertion, we can answer the following queries in asymptotically optimal time: - Test in constant time if two query vertices v and w are 2-edge-connected. Moreover, if v and w are not 2-edge-connected, we can produce in constant time a "witness" of this property, by exhibiting an edge that is contained in all paths from v to w or in all paths from w to v. - Report in O(n) time all the 2-edge-connected blocks of G. This is the first dynamic algorithm for 2-connectivity problems on directed graphs, and it matches the best known bounds for simpler problems, such as incremental transitive closure.
关键词：2-edge connectivity on directed graphs; dynamic graph algorithms; incremental algorithms.