On approximation intractability of the path–distance–width problem |
| |
Authors: | Koichi Yamazaki |
| |
Institution: | Department of Computer Science Gunma University, 1-5-1 Tenjin-cho, Kiryu zip:376-8515, Gunma, Japan |
| |
Abstract: | Path–distance–width of a graph G=(V,E), denoted by pdw(G), is the minimum integer k satisfying that there is a nonempty subset of S V such that the number of the nodes with distance i from S is at most k for any nonnegative integer i. It is known that given a positive integer k and a graph G, the decision problem pdw(G) k is NP-complete even if G is a tree (Yamazaki et al. Lecture Notes in Computer Science, vol. 1203, Springer, Berlin, 1997, pp. 276–287). In this paper, we show that it is NP-hard to approximate the path–distance–width of a graph within a ratio
for any >0, even for trees. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|