O(|E||X|) approximation algorithm that finds a directly NA-connected spanning subgraph with an edge nummber 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.)" />


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

Hiro ITO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.3   pp.363-370
Publication Date: 1995/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 7th Karuizawa Workshop on Circuits and Systems)
Category: Graphs and Networks
Keyword: 
telecommunication network,  graph,  connectivity,  disaster,  area,  

Full Text: PDF(629.8KB)>>
Buy this Article




Summary: 
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 nummber 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.)