Name
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 4 3 −ε for any ε >0, even for trees. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S0166-218X(00)00275-4 | Discrete Applied Mathematics |
Keywords | Field | DocType |
width problem,approximation intractability,decision problem,satisfiability | Graph theory,Integer,Discrete mathematics,Graph,Combinatorics,Graph toughness,Decision problem,Bound graph,Mathematics | Journal |
Volume | Issue | ISSN |
110 | 2-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
5 | 0.45 | 7 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Koichi Yamazaki | 1 | 222 | 21.85 |