Inferring Rooted Evolutionary Trees from Lowest Common Ancestor Constraints

スポンサーリンク

概要

• 論文の詳細を見る

• We study two optimization problems related to evolutionary tree construction called the maximum LCA constraints consistency problem (MLCC) and maximum 3-leaf constraints consistency problem (M3LCC). First, we prove that MLCC and M3LCC are NP-hard. Next, we provide a simple, fast approximation algorithm for both problems yielding solutions which are always within one third of the optimum. Finally, we present a more specialized polynomial-time approximation algorithm for M3LCC. The results in this paper have previously been published in [3] and [6].

• 社団法人電子情報通信学会の論文
• 2001-10-12

著者

• Jansson J

  Lund Univ. Lund Swe

• Jansson Jesper

  Dept. Of Computer Science Lund University

• GASIENIEC Leszek

  Dept. of Computer Science, University of Liverpool

• LINGAS Andrzej

  Dept. of Computer Science, Lund University

• OSTLIN Anna

  Dept. of Computer Science, Lund University

• Gasieniec Leszek

  Dept. Of Computer Science University Of Liverpool

• Lingas Andrzej

  Dept. Of Computer Science Lund University

• Ostlin Anna

  Dept. Of Computer Science Lund University

関連論文

• Inferring Rooted Evolutionary Trees from Lowest Common Ancestor Constraints

スポンサーリンク