NA-edge-connectivity augmentation problems by adding edges

NA-edge-connectivity augmentation problems by adding edges

0.00 Avg rating0 Votes
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: ,
Keywords: optimization
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.