Who is Who in Phylogenetic Networks

Publications related to 'cactus graph' : A connected graph in which any two simple cycles have at most one vertex in common (Wikipedia), generalizes trees and galled trees.   Order by:   Type | Year

Only And Or     related to:

Associated keywords

abstract-network cactus-graph counting explicit-network from-distances from-splits galled-tree level-k-phylogenetic-network optimal-realization phylogenetic-network phylogeny polynomial reconstruction

2020

1 Momoko Hayamizu, Katharina Huber, Vincent Moulton and Yukihiro Murakami. Recognizing and realizing cactus metrics. In IPL, Vol. 157(105916):1-5, 2020. Keywords: cactus graph, from distances, level k phylogenetic network, optimal realization, polynomial. Note: https://doi.org/10.1016/j.ipl.2020.105916.

2016

2 Nikita Alexeev and Max A. Alekseyev. Combinatorial Scoring of Phylogenetic Networks. In COCOON16, Vol. 9797:560-572 of LNCS, Springer, 2016. Keywords: cactus graph, counting, explicit network, galled tree, phylogenetic network, phylogeny. Note: http://arxiv.org/abs/1602.02841.

2009

3 Ulrik Brandes and Sabine Cornelsen. Phylogenetic Graph Models Beyond Trees. In DAM, Vol. 157(10):2361-2369, 2009. Keywords: abstract network, cactus graph, from splits, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.inf.uni-konstanz.de/~cornelse/Papers/bc-pgmbt-07.pdf.         Toggle abstract "A graph model for a set S of splits of a set X consists of a graph and a map from X to the vertices of the graph such that the inclusion-minimal cuts of the graph represent S. Phylogenetic trees are graph models in which the graph is a tree. We show that the model can be generalized to a cactus (i.e. a tree of edges and cycles) without losing computational efficiency. A cactus can represent a quadratic rather than linear number of splits in linear space. We show how to decide in linear time in the size of a succinct representation of S whether a set of splits has a cactus model, and if so construct it within the same time bounds. As a byproduct, we show how to construct the subset of all compatible splits and a maximal compatible set of splits in linear time. Note that it is N P-complete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models. © 2008 Elsevier B.V. All rights reserved."