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









Ulrik Brandes and
Sabine Cornelsen. Phylogenetic Graph Models Beyond Trees. In DAM, Vol. 157(10):23612369, 2009. Keywords: abstract network, cactus graph, from splits, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.inf.unikonstanz.de/~cornelse/Papers/bcpgmbt07.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 inclusionminimal 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 Pcomplete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models. © 2008 Elsevier B.V. All rights reserved."



