@inproceedings{2e5e6bd4e758407c94a6fad35e270125,

title = "Efficient optimization of monotonic functions on trees",

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 {\textquoteleft}monotonic{\textquoteright}. 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.",

author = "Yehoshua Perl and Yossi Shiloach",

year = "1981",

month = jan,

day = "1",

doi = "10.1007/3-540-10828-9_73",

language = "English (US)",

isbn = "9783540108283",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "332--339",

editor = "Egidio Astesiano and Corrado Bohm",

booktitle = "CAAP 1981",

address = "Germany",

note = "6th Colloquium on Trees in Algebra and Programming, CAAP 1981 ; Conference date: 05-03-1981 Through 07-03-1981",

}