TY - GEN
T1 - Efficient optimization of monotonic functions on trees
AU - Perl, Yehoshua
AU - Shiloach, Yossi
N1 - Publisher Copyright:
© 1981, Springer-Verlag.
PY - 1981
Y1 - 1981
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84911731879&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84911731879&partnerID=8YFLogxK
U2 - 10.1007/3-540-10828-9_73
DO - 10.1007/3-540-10828-9_73
M3 - Conference contribution
AN - SCOPUS:84911731879
SN - 9783540108283
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 332
EP - 339
BT - CAAP 1981
A2 - Astesiano, Egidio
A2 - Bohm, Corrado
PB - Springer Verlag
T2 - 6th Colloquium on Trees in Algebra and Programming, CAAP 1981
Y2 - 5 March 1981 through 7 March 1981
ER -