Name
Abstract | ||
|---|---|---|
The Binary Identification Problem for weighted trees asks for the minimum cost strategy (decision tree) for identifying a vertex in an edge weighted tree via testing edges. Each edge has assigned a different cost, to be paid for testing it. Testing an edge e reveals in which component of T-e lies the vertex to be identified. We give a complete characterization of the computational complexity of this problem with respect to both tree diameter and degree. In particular, we show that it is strongly NP-hard to compute a minimum cost decision tree for weighted trees of diameter at least 6, and for trees having degree three or more. For trees of diameter five or less, we give a polynomial time algorithm. Moreover, for the degree 2 case, we significantly improve the straightforward O(n^3) dynamic programming approach, and provide an O(n^2) time algorithm. Finally, this work contains the first approximate decision tree construction algorithm that breaks the barrier of factor logn. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.tcs.2012.06.023 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
binary identification problem,edge e,different cost,tree diameter,minimum cost decision tree,decision tree,polynomial time algorithm,weighted tree,edge weighted tree,minimum cost strategy,approximate decision tree construction | Journal | 459, |
ISSN | Citations | PageRank |
0304-3975 | 5 | 0.45 |
References | Authors | |
17 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ferdinando Cicalese | 1 | 450 | 48.20 |
| Tobias Jacobs | 2 | 54 | 4.32 |
| Eduardo Laber | 3 | 43 | 5.55 |
| Caio Valentim | 4 | 5 | 1.46 |