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
SN - 0304-3975
VL - 19
SP - 1
EP - 16
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1
ER -