Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/144270
Title: ON THE TREE AND CLUSTER CONTAINMENT PROBLEMS FOR PHYLOGENETIC NETWORKS
Authors: ANDREAS DWI MARYANTO GUNAWAN
ORCID iD:   orcid.org/0000-0003-0416-6377
Keywords: phylogenetics, tree containment, cluster containment, reticulation-visible
Issue Date: 26-Jan-2018
Citation: ANDREAS DWI MARYANTO GUNAWAN (2018-01-26). ON THE TREE AND CLUSTER CONTAINMENT PROBLEMS FOR PHYLOGENETIC NETWORKS. ScholarBank@NUS Repository.
Abstract: The tree containment problem (TCP) and cluster containment problem (CCP) are two fundamental problems arising from verification of network model for evolution. These problems are NP-hard for arbitrary networks. A lot of effort has been devoted to find network classes where these problems can be solved quickly. A bottleneck 7-years conjecture asks whether the TCP is solvable in polynomial time if the network input is reticulation-visible. In this paper, we present a positive answer to the conjecture and present a quadratic-time TCP algorithm for arbitrary reticulation-visible networks. While studying the problem, we discover a novel network decomposition that is useful in dealing with TCP and CCP. We then study the applications of this decomposition, and construct several TCP and CCP algorithms for some network classes. We also established a linear-time transformation from CCP instance to SAT instance, which opens up a possibility for creating faster CCP algorithms in the future.
URI: http://scholarbank.nus.edu.sg/handle/10635/144270
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
GunawanADM.pdf2.35 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

17
checked on Sep 20, 2018

Download(s)

9
checked on Sep 20, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.