Presentation | 1995/4/21 Approximation Algorithms for the Local Edge-Connectivity Augmentation Problem of Graphs Hirokazu Nakamasu, Toshiya Mashima, Toshimasa Watanabe, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | The local edge-connectivity augmentation problem (LECA for short) is to find a minimum-cost set of edges such that, by adding edges in the set to a given graph, in the resulting graph the number of edge disjoint paths is no less than the prescribed number given for each pair of vertices. In this paper, we give several approximation algorithms for LECA and evaluate them experimentally. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Graphs / Approximation algorithms / The local edge-connectivity augmentation problem / Local edge-connectivity of a graph |
Paper # | |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 1995/4/21(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 | Theoretical Foundations of Computing (COMP) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Approximation Algorithms for the Local Edge-Connectivity Augmentation Problem of Graphs |
Sub Title (in English) | |
Keyword(1) | Graphs |
Keyword(2) | Approximation algorithms |
Keyword(3) | The local edge-connectivity augmentation problem |
Keyword(4) | Local edge-connectivity of a graph |
1st Author's Name | Hirokazu Nakamasu |
1st Author's Affiliation | Hiroshima Prefectural Miyajima Technical High School() |
2nd Author's Name | Toshiya Mashima |
2nd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
3rd Author's Name | Toshimasa Watanabe |
3rd Author's Affiliation | Department of Circuits and System, Faculty of Engineering, Hiroshima University |
Date | 1995/4/21 |
Paper # | |
Volume (vol) | vol.95 |
Number (no) | 13 |
Page | pp.pp.- |
#Pages | 10 |
Date of Issue |