For Full-Text 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
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1998/05/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
graph, area graph, diameter, distance, connectivity, NP-complete, polynomial time, algorithm,
Full Text: PDF>>
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 NA-distance and the NA-(edge)-connectivity proposed and investigated in -. The NA-distance 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 NP-complete 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 NA-distance spanning subgraph problem considering the restrictions of the NA-distances and the sum of edge costs is NP-complete even if the following conditions are satisfied: all edge costs and all edge lengths are equal to one, the upper bound of the NA-distance 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 NA-distance and NA-edge-connectivity spanning subgraph problem considering the preservations of the NA-distances and the NA-edge-connectivity 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.