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 -