Connectivity Problems on Area Graphs for Locally Striking Disasters : Direct NA-Connection

概要

論文の詳細を見る
Connectivity (of node-to-node) is generally used to examine the robustness of graphs. When telecommunication network switches are integrated into logical switching areas, we should examine node-to-area connectivity rather than node-to-node connectivity. In a previous paper, we proposed node-to-area (NA) connectivity using area (subset of nodes) graph. In this paper, we consider a further constraint: "there is a path that does not include other nodes in the source node area. " We call this property, directly NA-connected. Application of this constraint makes telecommunications networks robust against locally striking disasters. The problem of finding the maximum number of edge deletions that still preserves the direct NA-connection is shown to be NP-hard. It was shown in our previous paper that an NA-connected spanning tree is easily found; this paper shows that the problem of finding a directly NA-connected spanning tree is also NP-hard. We propose an O(|E||X|) approximation algorithm that finds a directly NA-connected spanning subgraph with an edge number not exceeding 2|V|- 3 for any NA-connected area graph that satisfies a described simple condition. (|V|, |E|, and |X| are the numbers of nodes, edges, and areas, respectively.)
社団法人電子情報通信学会の論文
1995-03-25