SYSTEM AND METHOD FOR OPTIMALLY SELECTING LINK ADDITION PART, AND PROGRAM

摘要

PROBLEM TO BE SOLVED: To select an optimal link addition part for restraining a maximum path length increasing rate in a single link failure in a network. SOLUTION: This system for optimally selecting a link addition part includes: an input part 101 for storing, in a storage device, topology information G of a network and an upper-limit value K of a path length increasing rate input through an input device; a link addition part selection part 102 for selecting a link addition part minimizing the number of links to be added to set all the increasing rates of path length by a single link failure not larger than the upper limit value by executing a process according to an approximate algorithm for a collective cover problem using the topology information G of the network and the upper-limit value K of the path length increasing rate stored in the storage device; and an output part for outputting the link addition part selected by the link addition part selection part 102 to an output device; and can satisfy failure resistance and the path length increasing rate at a desired connection degree in the network with minimum link addition to improve reliability and quality of the network. COPYRIGHT: (C)2010,JPO&INPIT