Perfect Phylogenies via Branchings in Acyclic Digraphs and a Generalization of Dilworth’s Theorem

DOI10.1145/3182178zbMath1454.92023arXiv1701.05492OpenAlexW3123103866MaRDI QIDQ4554347

Romeo Rizzi, Edin Husić, Martin Milanič, Ademir Hujdurović, Alexandru I. Tomescu

Publication date: 13 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1701.05492

zbMATH Keywords

approximation algorithmbranchingmin-max theoremAPX-hardnessacyclic digraphchain partitionDilworth's theoremperfect phylogenyminimum conflict-free row split problem

Mathematics Subject Classification ID

Problems related to evolution (92D15) Applications of graph theory (05C90) Genetics and epigenetics (92D10) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Weighted Rooted Trees: Fat or Tall? ⋮ Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples ⋮ Speedup the optimization of maximal closure of a node-weighted directed acyclic graph

This page was built for publication: Perfect Phylogenies via Branchings in Acyclic Digraphs and a Generalization of Dilworth’s Theorem