Back to activities
GERAD seminar

Fully leafed induced subtrees


Apr 19, 2018   03:30 PM — 04:30 PM

Élise Vandomme LACIM, Université du Québec à Montréal, Canada

Subtrees of graphs, as well as their number of leaves, have been investigated by various communities: from discrete mathematics to data mining and information retrieval. We consider a variant where we require the subtrees to be induced and compute their maximal number of leaves. The problem, which is NP-complete in general, becomes polynomial in the case of trees. The leaf function associates to a number n the maximal number of leaves an induced subtree of size n can have. To compute the leaf function, we provide an efficient branch and bound algorithm. In the particular case of trees, we describe a polynomial algorithm using the dynamic programming paradigm. We conclude by exhibiting a link between the leaf functions of caterpillar graphs and a particular class of words called prefix normal.

Free entrance.
Welcome to everyone!

Eglantine Camby organizer


Room 4488
André-Aisenstadt Building
Université de Montréal Campus
2920, chemin de la Tour Montréal QC H3T 1J4 Canada