On the complexity of edge labelings for trees

Y. Perl; S. Zaks

doi:10.1016/0304-3975(82)90011-1

On the complexity of edge labelings for trees

Y. Perl
, S. Zaks

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	1-16
Number of pages	16
Journal	Theoretical Computer Science
Volume	19
Issue number	1
DOIs	https://doi.org/10.1016/0304-3975(82)90011-1
State	Published - Jul 1982
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/0304-3975(82)90011-1

Cite this

@article{918344e549134afa8af83f687217cdae,

title = "On the complexity of edge labelings for trees",

abstract = "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).",

author = "Y. Perl and S. Zaks",

note = "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.",

year = "1982",

month = jul,

doi = "10.1016/0304-3975(82)90011-1",

language = "English (US)",

volume = "19",

pages = "1--16",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

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 - https://www.scopus.com/pages/publications/0346625898

UR - https://www.scopus.com/pages/publications/0346625898#tab=citedBy

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 -

On the complexity of edge labelings for trees

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this