Geodesic
Treewidth of display graphs: bounds, brambles and applications
Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 4, pp. 715-743.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Phylogenetic trees and networks are leaf-labelled graphs used to model evolution. Display graphs are created by identifying common leaf labels in two or more phylogenetic trees or networks. The treewidth of such graphs is bounded as a function of many common dissimilarity measures between phylogenetic trees and this has been leveraged in fixed parameter tractability results. Here we further elucidate the properties of display graphs and their interaction with treewidth. We show that it is NP-hard to recognize display graphs, but that display graphs of bounded treewidth can be recognized in linear time. Next we show that if a phylogenetic network displays (i.e. topologically embeds) a phylogenetic tree, the treewidth of their display graph is bounded by a function of the treewidth of the original network (and also by various other parameters). In fact, using a bramble argument we show that this treewidth bound is sharp up to an additive term of 1. We leverage this bound to give an FPT algorithm, parameterized by treewidth, for determining whether a network displays a tree, which is an intensively-studied problem in the field. We conclude with a discussion on the future use of display graphs and treewidth in phylogenetics.
DOI : 10.7155/jgaa.00508
Keywords: display graph, phylogenetic tree, treewidth, fixed parameter tractability, monadic second order logic 
@article{JGAA_2019_23_4_a4,
     author = {Remie Janssen and Mark Jones and Steven Kelk and Georgios Stamoulis and Taoyang Wu},
     title = {Treewidth of display graphs: bounds, brambles and applications},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {715--743},
     publisher = {mathdoc},
     volume = {23},
     number = {4},
     year = {2019},
     doi = {10.7155/jgaa.00508},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00508/}
}
TY  - JOUR
AU  - Remie Janssen
AU  - Mark Jones
AU  - Steven Kelk
AU  - Georgios Stamoulis
AU  - Taoyang Wu
TI  - Treewidth of display graphs: bounds, brambles and applications
JO  - Journal of Graph Algorithms and Applications
PY  - 2019
SP  - 715
EP  - 743
VL  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00508/
DO  - 10.7155/jgaa.00508
LA  - en
ID  - JGAA_2019_23_4_a4
ER  - 
%0 Journal Article
%A Remie Janssen
%A Mark Jones
%A Steven Kelk
%A Georgios Stamoulis
%A Taoyang Wu
%T Treewidth of display graphs: bounds, brambles and applications
%J Journal of Graph Algorithms and Applications
%D 2019
%P 715-743
%V 23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00508/
%R 10.7155/jgaa.00508
%G en
%F JGAA_2019_23_4_a4
Remie Janssen; Mark Jones; Steven Kelk; Georgios Stamoulis; Taoyang Wu. Treewidth of display graphs: bounds, brambles and applications. Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 4, pp. 715-743. doi : 10.7155/jgaa.00508. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00508/

Cité par Sources :