| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652933 | Electronic Notes in Discrete Mathematics | 2007 | 5 Pages |
Abstract
Given a graph G=(V,E), a positive integer k, and a positive integer d, we want find a subset Vk with k vertices such the graph obtained by identifying the vertices from Vk in G has diameter at most d. We prove that for every d⩾2 the problem is NP-complete. For the case of trees we provide a polynomial time algorithm that exploits the relationship with the r-dominating set problem.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
