| Presentation | 2000/11/2 An Efficient Distributed Algorithm DECA-1 for the (σ+1)-Edge-Connectivity Augmentation Problem of Communication Networks Yasuhiro Kurose, Toshiyuki Okamoto, Satoshi Taoka, Toshimasa Watanabe, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The graph of a given communication network is a graph G = (V, E) obtained by representing each node and each link of this network as a vertex and an edges, respectively. The (σ+1)-edge-connectivity augmentation problem of communication networks ((σ+1)ECAN) is the problem of finding a minimum set of edges (links) E′ such that (V, E∪E′) is (σ+1)-edge-connected when the graph G = (V, E) of a given network is σ-edge-connected. A distributed algorithm for the problem means finding a solution by communication through a given network. This paper first shows how to obtain a solution E′ to (σ+1)ECAN such that, for any minimum cut of G, E′ contains constant number of edges crossing this cut. Then, as an application of this result, we propose a distributed one DECA - 1, with time complexity T = O(T(|V|, |E|)+|V|) and communication complexity C = O(C(|V|, |E|)+|E|), for (σ+1)ECAN with σ ≥ 1 and G satisfying certain conditions, where T(|V|, |E|) or C(|V|, |E|) denotes time complexity or communication complexity of any distributed algorithm, for finding all (σ+1)-edge-connected components S of G: in particular, T = O(|V|), and C = O(|E|) for σ = 1. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | (σ+1)-edge-connectivity augmentation problems / Distributed algorithms / Communication networks / Time complexity / Communication complexity |
| Paper # | CAS 2000-62,CST 2000-17 |
| Date of Issue |
| Conference Information | |
| Committee | CAS |
|---|---|
| Conference Date | 2000/11/2(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Circuits and Systems (CAS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Efficient Distributed Algorithm DECA-1 for the (σ+1)-Edge-Connectivity Augmentation Problem of Communication Networks |
| Sub Title (in English) | |
| Keyword(1) | (σ+1)-edge-connectivity augmentation problems |
| Keyword(2) | Distributed algorithms |
| Keyword(3) | Communication networks |
| Keyword(4) | Time complexity |
| Keyword(5) | Communication complexity |
| 1st Author's Name | Yasuhiro Kurose |
| 1st Author's Affiliation | Graduate School of Engineering, Hiroshima University() |
| 2nd Author's Name | Toshiyuki Okamoto |
| 2nd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
| 3rd Author's Name | Satoshi Taoka |
| 3rd Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 4th Author's Name | Toshimasa Watanabe |
| 4th Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| Date | 2000/11/2 |
| Paper # | CAS 2000-62,CST 2000-17 |
| Volume (vol) | vol.100 |
| Number (no) | 415 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |