
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Connectivity Problems on Area Graphs for Locally Striking DisastersDirect NAConnection
Hiro ITO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E78A
No.3
pp.363370 Publication Date: 1995/03/25
Online ISSN:
DOI:
Print ISSN: 09168508 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)>>
Summary:
Connectivity (of nodetonode) is generally used to examine the robustness of graphs. When telecommunication network switches are integrated into logical switching areas, we should examine nodetoarea connectivity rather than nodetonode connectivity. In a previous paper, we proposed nodetoarea (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 NAconnected. 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 NAconnection is shown to be NPhard. It was shown in our previous paper that an NAconnected spanning tree is easily found; this paper shows that the problem of finding a directly NAconnected spanning tree is also NPhard. We propose an O(EX) approximation algorithm that finds a directly NAconnected spanning subgraph with an edge nummber not exceeding 2V3 for any NAconnected area graph that satisfies a described simple condition. (V,E,and X are the numbers of nodes, edges, and areas, respectively.)

