Article ID: | iaor20051914 |
Country: | Japan |
Volume: | 47 |
Issue: | 4 |
Start Page Number: | 224 |
End Page Number: | 243 |
Publication Date: | Dec 2004 |
Journal: | Journal of the Operations Research Society of Japan |
Authors: | Ito Hiro, Miwa Hiroyoshi |
Keywords: | optimization |
The network reliability in multi-server environment is measured by the connectivity between a vertex and a vertex subset (NA-connectivity). The problem of augmenting a graph by adding the smallest number of new edges to meet NA-edge(vertex)-connectivity requirement is an important optimization problem that contributes to the network design problem to increase the reliability of a current network by adding the smallest number of links. This problem is a generalization of the well-known connectivity augmentation problems. In this paper, we focus on the NA-edge-connectivity augmentation problem. First, we prove the NP-completeness of the problem which determines whether we can augment a graph to a 1-NA-edge-connected graph by adding a given number or less new edges. Next, we prove that the problem of augmenting a 1-NA-edge connected graph or a 0-NA-edge-connected graph to be 2-NA-edge-connected graph by adding the smallest number of edges can be solved in polynomial time.