| Presentation | 1994/1/26 Approximation Algorithms for the Minimum-Cost 3-Connectivity Augmentation Problem of Graphs Hiroyuki Kawai, Toshiya Mashima, Satoshi Taoka, Toshimasa Watanabe, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The paper proposes three approximation algorithms MCM,SMC,and MCF for the minimum-cost 3-connectivity augmentation problem(W-3- VCA)defind by ″Given a complete graph G=(V,E),its spanning subgrap h G_0=(V,E′)and nonnegative integer costs c(e)for edges e∈E such that c(e′)=0 if e′∈E′ and c(e″)>0 if e″∈E-E′,find a minimum -cost set of edges to be added so as to 3-connect G_0.″Their exper imental evaluation shows that MCM based on finding a maximum-cost matching shows the best performance in general. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | 3-connectivity augmentation problems / vertex-connectivity / approximation algorithms / 3-vertex-connected graph / maximum- cost matching |
| Paper # | COMP93-74 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1994/1/26(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 Minimum-Cost 3-Connectivity Augmentation Problem of Graphs |
| Sub Title (in English) | |
| Keyword(1) | 3-connectivity augmentation problems |
| Keyword(2) | vertex-connectivity |
| Keyword(3) | approximation algorithms |
| Keyword(4) | 3-vertex-connected graph |
| Keyword(5) | maximum- cost matching |
| 1st Author's Name | Hiroyuki Kawai |
| 1st Author's Affiliation | Department of Circuits and Systems,Faculty of Engineering, Hiroshima University() |
| 2nd Author's Name | Toshiya Mashima |
| 2nd Author's Affiliation | Department of Circuits and Systems,Faculty 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 | 1994/1/26 |
| Paper # | COMP93-74 |
| Volume (vol) | vol.93 |
| Number (no) | 438 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |