For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Efficient Algorithms to Augment the Edge-Connectivity of Specified Vertices by One in a GraphSatoshi TAOKA  Toshimasa WATANABE  Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.2   pp.379-388Publication Date: 2019/02/01 Online ISSN: 1745-1337 DOI: 10.1587/transfun.E102.A.379 Type of Manuscript: Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)Category: Keyword: graphs,  connectivity augmentation,  edge-connectivity,  edge-interchange operations,  polynomial time algorithms,  Full Text: PDF(670.3KB)>> Buy this Article Summary:  The k-edge-connectivity augmentation problem for a specified set of vertices (kECA-SV for short) is defined by “Given a graph G=(V, E) and a subset Γ ⊆ V, find a minimum set E' of edges such that G'=(V, E ∪ E') has at least k edge-disjoint paths between any pair of vertices in Γ.” Let σ be the edge-connectivity of Γ (that is, G has at least σ edge-disjoint paths between any pair of vertices in Γ). We propose an algorithm for (σ+1)ECA-SV which is done in O(|Γ|) maximum flow operations. Then the time complexity is O(σ2|Γ||V|+|E|) if a given graph is sparse, or O(|Γ||V||BG|log(|V|2/|BG|)+|E|) if dense, where |BG| is the number of pairs of adjacent vertices in G. Also mentioned is an O(|V||E|+|V|2 log |V|) time algorithm for a special case where σ is equal to the edge-connectivity of G and an O(|V|+|E|) time one for σ ≤ 2.