
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.

Sparse Spanning Subgraphs Preserving Connectivity and Distance between Vertices and Vertex Subsets
Hiroyoshi MIWA Hiro ITO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E81A
No.5
pp.832841 Publication Date: 1998/05/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: graph, area graph, diameter, distance, connectivity, NPcomplete, polynomial time, algorithm,
Full Text: PDF(821.4KB)>>
Summary:
This paper investigates the relations between the computational complexity and the restrictions for several problems that determine whether a given graph with edge costs and edge lengths has a spanning subgraph with such restrictions as the diameter, the connectivity, and the NAdistance and the NA(edge)connectivity proposed and investigated in [1][5]. The NAdistance and the NA(edge)connectivity are the measures for the distance and the connectivity between a vertex and a vertex subset (area). In this paper we prove that the minimum diameter spanning subgraph problem considering the restrictions of the diameter and the sum of edge costs is NPcomplete even if the following restrictions are satisfied: all edge costs and all edge lengths are equal to one, and the upper bound of the diameter is restricted to four. Next, we prove that the minimum NAdistance spanning subgraph problem considering the restrictions of the NAdistances and the sum of edge costs is NPcomplete even if the following conditions are satisfied: all edge costs and all edge lengths are equal to one, the upper bound of the NAdistance is restricted to four, each area is composed of a vertex, and the number of areas is restricted to two. Finally, we investigate the preserving NAdistance and NAedgeconnectivity spanning subgraph problem considering the preservations of the NAdistances and the NAedgeconnectivity and the restrictions of the sum of edge costs, and prove that a sparse spanning subgraph can be constructed in polynomial time if all edge costs are equal to one.

