An approximation algorithm for bounded degree closest phylogenetic 2nd root problem

Autor:	Md. Rafiqul Islam, Md. Ahsanur Rahman
Rok vydání:	2010
Předmět:	Combinatorics Mathematical optimization Approximation theory Degree (graph theory) Computational complexity theory Phylogenetic tree Bounded function Approximation algorithm Graph (abstract data type) Constant (mathematics) Mathematics
Zdroj:	2010 13th International Conference on Computer and Information Technology (ICCIT).
DOI:	10.1109/iccitechn.2010.5723821
Popis:	The degree Δ-closest phylogenetic 2nd root problem (ΔCPR 2 ) is an NP-hard problem concerning phylogenetic tree reconstruction from a graph representing the similarities of the species concerned. Here we present an approximation algorithm for this problem for any fixed Δ > 3. When |V| > 3Δ − 1, our algorithm yields an approximation ratio of max((Δ−2)/α, 2), where α > 1 is a constant whose value depends on the values of |V| and Δ.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::f4058d152015150a2985dcb2cd694adf https://doi.org/10.1109/iccitechn.2010.5723821 Zobrazit plný text záznamu