[en] 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 provide a polynomial algorithm using the dynamic programming paradigm.
Disciplines :
Mathematics
Author, co-author :
Vandomme, Elise ; Université de Liège - ULiège > Département de mathématique > Probabilités et statistique mathématique
Language :
English
Title :
Fully leafed induced subtrees
Publication date :
June 2018
Event name :
Cologne-Twente Workshop on Graphs and Combinatorial Optimization