Determining the consistency of resolved triplets and fan triplets

Jesper Andreas Jansson, Andrzej Lingas, Ramesh Rajaby, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

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 paper 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.
Original languageEnglish
Title of host publicationResearch in Computational Molecular Biology - 21st Annual International Conference, RECOMB 2017, Proceedings
PublisherSpringer Verlag
Pages82-98
Number of pages17
ISBN (Print)9783319569697
DOIs
Publication statusPublished - 1 Jan 2017
Event21st Annual International Conference on Research in Computational Molecular Biology, RECOMB 2017 - Hong Kong, Hong Kong
Duration: 3 May 20177 May 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10229 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st Annual International Conference on Research in Computational Molecular Biology, RECOMB 2017
CountryHong Kong
CityHong Kong
Period3/05/177/05/17

Keywords

  • Algorithm
  • Computational complexity
  • Phylogenetic tree
  • Rooted triplets consistency

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this