On the complexity of edge labelings for trees

Y. Perl, S. Zaks

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)1-16
Number of pages16
JournalTheoretical Computer Science
Volume19
Issue number1
DOIs
StatePublished - Jul 1982
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the complexity of edge labelings for trees'. Together they form a unique fingerprint.

Cite this