Efficient optimization of monotonic functions on trees

Yehoshua Perl, Yossi Shiloach

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

The problem of optimizing weighting functions over all the k-subtrees (subtrees with k vertices) of a given tree, is considered. A general algorithm is presented, that finds an optimal k-subtree of a given tree whenever the weighting function is what we call ‘monotonic’. Monotonicity is a very natural property, satisfied by most of the functions that one can think of. The problem is solved for both cases of rooted and undirected trees. On the ohter hand, even simple extensions of it to general graphs are NP-hard.

Original languageEnglish (US)
Title of host publicationCAAP 1981
Subtitle of host publicationTrees in Algebra and Programming - 6th Colloquium, Proceedings
EditorsEgidio Astesiano, Corrado Bohm
PublisherSpringer Verlag
Pages332-339
Number of pages8
ISBN (Print)9783540108283
DOIs
StatePublished - Jan 1 1981
Externally publishedYes
Event6th Colloquium on Trees in Algebra and Programming, CAAP 1981 - Genoa, Italy
Duration: Mar 5 1981Mar 7 1981

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume112 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th Colloquium on Trees in Algebra and Programming, CAAP 1981
CountryItaly
CityGenoa
Period3/5/813/7/81

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficient optimization of monotonic functions on trees'. Together they form a unique fingerprint.

Cite this