Determining the consistency of resolved triplets and fan triplets

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

Abstract

The R+-F+-Consistency problem takes as input two sets R+ and R- of resolved triplets and two sets F+ and F- of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in R+ ⊂ F+ and no elements in R- ⊂ F- as embedded subtrees, if such a tree exists. This article presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying R-=θ whose running time is linear in the size of the input and therefore optimal.

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • Hong Kong Polytechnic University
  • National University of Singapore
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Matematik

Nyckelord

Originalspråkengelska
Sidor (från-till)740-754
Antal sidor15
TidskriftJournal of Computational Biology
Volym25
Utgåva nummer7
StatusPublished - 2018 jul 1
PublikationskategoriForskning
Peer review utfördJa