No full text
Scientific conference in universities or research centers (Scientific conferences in universities or research centers)
Fully leafed induced subtrees
Vandomme, Elise
2018
 

Files


Full Text
No document available.

Send to



Details



Abstract :
[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 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.
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 :
April 2018
Event name :
Seminar of the research center GERAD
Event place :
Montreal, Canada
Event date :
13/04/2018
Available on ORBi :
since 03 May 2019

Statistics


Number of views
14 (0 by ULiège)
Number of downloads
0 (0 by ULiège)

Bibliography


Similar publications



Contact ORBi