Abstract | ||
---|---|---|
Ellis et al., proposed algorithms (in terms of vertexsep aration) to compute the node-search number of an n-vertextree T in O(n) time and to construct an optimal node-search strategy of T in O(n log n) time. An open problem is whether the latter can also be done in linear time. In this paper, we solve this open problem by exploring fundamental graph theoretical properties. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1007/3-540-68535-9_32 | COCOON |
Keywords | Field | DocType |
fundamental graph,optimal node-search strategy,open problem,vertexsep aration,node-search number,linear-time algorithm,n log n,linear time,theoretical property,proposed algorithm,computational complexity | Graph theory,Discrete mathematics,Graph,Combinatorics,Open problem,Algorithm complexity,Computer science,Algorithm,Time complexity,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
3-540-64824-0 | 1 | 0.36 |
References | Authors | |
17 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sheng-lung Peng | 1 | 173 | 20.25 |
Chin-Wen Ho | 2 | 573 | 39.27 |
Tsan-sheng Hsu | 3 | 737 | 101.00 |
Ming-Tat Ko | 4 | 1320 | 103.71 |
Chuan Yi Tang | 5 | 704 | 79.25 |