Alok Aggarwal, Maria Klawe
Discrete Applied Mathematics
A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that whenever x, y and z are the labels of vertices on a path of length 2 then y≦(x+z)/2. In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a tree T is the smallest integer m such that T has a convex labelling with no label greater than m. We prove that every rooted tree (and hence every tree) with n vertices has convex label number less than 4 n. We also exhibit n-vertex trees with convex label number 4 n/3+o(n), and n-vertex rooted trees with convex label number 2 n +o(n). © 1987 Akadémiai Kiadó.
Alok Aggarwal, Maria Klawe
Discrete Applied Mathematics
Maria Klawe, Wolfgang J. Paul, et al.
STOC 1984
Alok Aggarwal, Maria Klawe, et al.
Algorithmica
Alok Aggarwal, Maria Klawe, et al.
Algorithmica