Given a tree T with n edges and a set W of n weights, we deal with labelings of the edges of T with weights from W, optimizing certain objective functions. For some of these functions the optimization problem is shown to be NP-complete (e.g., finding a labeling with minimal diameter), and for others we find polynomial-time algorithms (e.g., finding a labeling with minimal average distance).
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)