Speaker
Mrs
Nina Haug
(Alpen-Adria-Universität Klagenfurt / TU Graz)
Description
We consider the following question: Among all trees that have the same (given) degree sequence, find a tree with the minimal number of subtrees.
While it is already known that the unique solution of the analogous maximisation problem is the "greedy tree", the solution of the minimisation problem is more com- plex. In the talk, we develop a polynomial time algorithm for finding an optimal solution of the minimisation problem.
Primary author
Mrs
Nina Haug
(Alpen-Adria-Universität Klagenfurt / TU Graz)
Co-authors
Mr
Clemens Heuberger
(Alpen-Adria-Universität Klagenfurt)
Mr
Hua Wang
(Georgia Southern University)
