Phylogenetic diversity and the maximum coverage problem

✍ Scribed by Vincent Moulton; Andreas Spillner

• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 376 KB
• Volume: 22
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/j.aml.2009.03.017

✦ Synopsis

For a weighted hypergraph (H, ω), with vertex set X , edge set E, and weighting ω : E → R ≥0 , the maximum coverage problem is to find a k-element subset Y ⊆ X that maximizes the total weight of those edges that have non-empty intersection with Y among all k-element subsets of X . Such a subset Y is called optimal. Recently, within the field of phylogenetics it has been shown that for certain weighted hypergraphs coming from phylogenetic trees the collection of optimal subsets of X forms a so-called strong greedoid. We call hypergraphs having this latter property strongly greedy. In this note we characterize the r-uniform hypergraphs H with unit edge weights that are strongly greedy in the case where r is a prime number.