Groupe d’études et de recherche en analyse des décisions

Fully leafed induced subtrees

É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.

Entrée gratuite.
Bienvenue à tous!