@InProceedings{jansson10complexity,
  author    = {Jansson, Jesper and Lemence, RichardS. and Lingas, Andrzej},
  title     = {The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree},
  booktitle = {Proc. of Workshop on Algorithms in Bioinformatics (WABI 2010)},
  year      = {2010},
  volume    = {6293},
  series    = lncs,
  pages     = {262--273},
  publisher = Springer,
  abstract  = {A recursive algorithm by Aho, Sagiv, Szymanski, and Ullman [1] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [4], the tree output by the algorithm of Aho et al. is not always minimal; there may exist other trees which contain fewer nodes yet are still consistent with the input. In this paper, we prove strong polynomial-time inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MinRS). We also present an exponential-time algorithm for solving MinRS exactly which is based on tree separators. It runs in 2^O(n log k) time when every node is required to have at most k children which are internal nodes and where n is the cardinality of the leaf label set of the input trees.},
  doi       = {10.1007/978-3-642-15294-8_22},
  isbn      = {978-3-642-15293-1},
  keywords  = {Phylogenetic tree; rooted triplet; minimally resolved supertree; NP-hardness; tree separator},
  owner     = {Sebastian},
  timestamp = {2014.10.09},
}

{"_id":"f5KdPzWkgjRizNL6W","bibbaseid":"jansson-lemence-lingas-thecomplexityofinferringaminimallyresolvedphylogeneticsupertree-2010","authorIDs":[],"author_short":["Jansson, J.","Lemence, R.","Lingas, A."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Jansson"],"firstnames":["Jesper"],"suffixes":[]},{"propositions":[],"lastnames":["Lemence"],"firstnames":["RichardS."],"suffixes":[]},{"propositions":[],"lastnames":["Lingas"],"firstnames":["Andrzej"],"suffixes":[]}],"title":"The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree","booktitle":"Proc. of Workshop on Algorithms in Bioinformatics (WABI 2010)","year":"2010","volume":"6293","series":"Lect Notes Comput Sci","pages":"262–273","publisher":"Springer, Berlin","abstract":"A recursive algorithm by Aho, Sagiv, Szymanski, and Ullman [1] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [4], the tree output by the algorithm of Aho et al. is not always minimal; there may exist other trees which contain fewer nodes yet are still consistent with the input. In this paper, we prove strong polynomial-time inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MinRS). We also present an exponential-time algorithm for solving MinRS exactly which is based on tree separators. It runs in 2^O(n log k) time when every node is required to have at most k children which are internal nodes and where n is the cardinality of the leaf label set of the input trees.","doi":"10.1007/978-3-642-15294-8_22","isbn":"978-3-642-15293-1","keywords":"Phylogenetic tree; rooted triplet; minimally resolved supertree; NP-hardness; tree separator","owner":"Sebastian","timestamp":"2014.10.09","bibtex":"@InProceedings{jansson10complexity,\n author = {Jansson, Jesper and Lemence, RichardS. and Lingas, Andrzej},\n title = {The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree},\n booktitle = {Proc. of Workshop on Algorithms in Bioinformatics (WABI 2010)},\n year = {2010},\n volume = {6293},\n series = lncs,\n pages = {262--273},\n publisher = Springer,\n abstract = {A recursive algorithm by Aho, Sagiv, Szymanski, and Ullman [1] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [4], the tree output by the algorithm of Aho et al. is not always minimal; there may exist other trees which contain fewer nodes yet are still consistent with the input. In this paper, we prove strong polynomial-time inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MinRS). We also present an exponential-time algorithm for solving MinRS exactly which is based on tree separators. It runs in 2^O(n log k) time when every node is required to have at most k children which are internal nodes and where n is the cardinality of the leaf label set of the input trees.},\n doi = {10.1007/978-3-642-15294-8_22},\n isbn = {978-3-642-15293-1},\n keywords = {Phylogenetic tree; rooted triplet; minimally resolved supertree; NP-hardness; tree separator},\n owner = {Sebastian},\n timestamp = {2014.10.09},\n}\n\n","author_short":["Jansson, J.","Lemence, R.","Lingas, A."],"key":"jansson10complexity","id":"jansson10complexity","bibbaseid":"jansson-lemence-lingas-thecomplexityofinferringaminimallyresolvedphylogeneticsupertree-2010","role":"author","urls":{},"keyword":["Phylogenetic tree; rooted triplet; minimally resolved supertree; NP-hardness; tree separator"],"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:42.152Z","downloads":0,"keywords":["phylogenetic tree; rooted triplet; minimally resolved supertree; np-hardness; tree separator"],"search_terms":["complexity","inferring","minimally","resolved","phylogenetic","supertree","jansson","lemence","lingas"],"title":"The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree","year":2010,"dataSources":["C5FtkvWWggFfMJTFX"]}