Enumerating vertices of the balanced minimum evolution polytope

Daniele Catanzaro, Raffaele Pesenti

Research output: Contribution to journalArticlepeer-review

Abstract

Recent advances on the polyhedral combinatorics of the Balanced Minimum Evolution Problem (BMEP) enabled the identification of fundamental characteristics of the convex hull of the BMEP (or BMEP polytope) as well as the description of some of its facets. These results have been possible thanks to the assistance of general purpose softwares for polyhedral analyses, such as Polymake, whose running times however become quickly unpractical. In this article, we address the problem of designing tailored algorithms for the study of the BMEP polytope, with special focus on the problem of enumerating its vertices. To this end, by exploiting some results from the polyhedral combinatorics of the BMEP and a particular encoding scheme based on Prüfer coding, we present an iterative enumeration algorithm that is markedly faster than current general purpose softwares and that can be natively massively parallelized.
Original languageEnglish
Pages (from-to)209-217
Number of pages9
JournalComputers and Operations Research
Volume109
DOIs
Publication statusPublished - 1 Sep 2019

Keywords

  • Balanced minimum evolution polytope
  • Parallel enumeration
  • Phylogenetics
  • Prüfer coding
  • Tree codes
  • Unrooted binary tree enumeration

Cite this