Sparse Spanning Subgraphs Preserving Connectivity and Distance between Vertices and Vertex Subsets(Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
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[1]-[5]. 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 an 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.
社団法人電子情報通信学会の論文
1998-05-25

Sparse Spanning Subgraphs Preserving Connectivity and Distance between Vertices and Vertex Subsets(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク