caa a22 4500 445855819 CHVBK 20180317145427.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00026-011-0093-6 doi (NATIONALLICENCE)springer-10.1007/s00026-011-0093-6 Optimizing Phylogenetic Diversity with Ecological Constraints [Elektronische Daten] [Beáta Faller, Charles Semple, Dominic Welsh] Given an edge-weighted tree $${\mathcal {T}}$$ with leaf set X, define the weight of a subset S of X as the sum of the edge-weights of the minimal subtree of $${\mathcal {T}}$$ connecting the elements in S. It is known that the problem of selecting subsets of X of a given size to maximize this weight can be solved using a greedy algorithm. This optimization problem arises in conservation biology where the weight is referred to as the phylogenetic diversity of a taxa set S. Here, we consider the extension of this problem whereby we are only interested in selecting subsets of the taxa set that are ecologically "viable”. Such subsets are specified by an acyclic digraph which represents, for example, a food web. This additional constraint makes the problem computationally hard. In this paper, we analyze the complexity of different variations of the extended problem. Springer Basel AG, 2011 phylogenetic tree nationallicence phylogenetic diversity nationallicence food web nationallicence Faller Beáta Institute of Mathematics, Eötvös Loránd University, Pázmány Péter sétány 1/C, H-1117, Budapest, Hungary aut Semple Charles Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, 8140, Christchurch, New Zealand aut Welsh Dominic Merton College, University of Oxford, Merton Street, OX1 4JD, Oxford, United Kingdom aut Annals of Combinatorics SP Birkhäuser Verlag Basel 15/2(2011-06-01), 255-266 0218-0006 15:2<255 2011 15 26 https://doi.org/10.1007/s00026-011-0093-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00026-011-0093-6 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Faller Beáta Institute of Mathematics, Eötvös Loránd University, Pázmány Péter sétány 1/C, H-1117, Budapest, Hungary aut NATIONALLICENCE 700 1- Semple Charles Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, 8140, Christchurch, New Zealand aut NATIONALLICENCE 700 1- Welsh Dominic Merton College, University of Oxford, Merton Street, OX1 4JD, Oxford, United Kingdom aut NATIONALLICENCE 773 0- Annals of Combinatorics SP Birkhäuser Verlag Basel 15/2(2011-06-01), 255-266 0218-0006 15:2<255 2011 15 26 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer