TY - JOUR

T1 - On the complexity of edge labelings for trees

AU - Perl, Y.

AU - Zaks, S.

N1 - Funding Information:
* This work was done while brJih authors were at the Department of Computer Scienl:e, University of Illinois at Urbana-Champaign, Urbana, Ii 618011, and was supp orted in part by the National Science Foundation under grant NSF MCS 77-22830.

PY - 1982/7

Y1 - 1982/7

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0346625898&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346625898&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(82)90011-1

DO - 10.1016/0304-3975(82)90011-1

M3 - Article

AN - SCOPUS:0346625898

VL - 19

SP - 1

EP - 16

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1

ER -