Sparse Spanning Subgraphs Preserving Connectivity and Distance between Vertices and Vertex Subsets

摘要

This paper investigates the relations between the computationalcomplexity and the restrictions for several prob- lems that determinewhether a given graph with edge costs and edge lengths has a spanningsubgraph with such restrictions as the diameter, the connectivity,and the NA-distance and the NA- (edge)-connectivity proposed andinvestigated n 1-5. The NA-distance and theNA-(edge)-connectivity are the measures for the distance and theconnectivity between a vertex and a vertex subset (area).