English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  On the complexity of computing evolutionary trees

Gasieniec, L., Jansson, J., Lingas, A., & Östlin, A.(1996). On the complexity of computing evolutionary trees (MPI-I-1996-1-031). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Files

show Files
hide Files
:
MPI-I-96-1-031.pdf (Any fulltext), 230KB
Name:
MPI-I-96-1-031.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Gasieniec, Leszek1, Author           
Jansson, Jesper2, Author
Lingas, Andrzej2, Author
Östlin, Anna2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: In this paper we study a few important tree optimization problems with applications to computational biology. These problems ask for trees that are consistent with an as large part of the given data as possible. We show that the maximum homeomorphic agreement subtree problem cannot be approximated within a factor of $N^{\epsilon}$, where $N$ is the input size, for any $0 \leq \epsilon < \frac{1}{18}$ in polynomial time, unless P=NP. On the other hand, we present an $O(N\log N)$-time heuristic for the restriction of this problem to instances with $O(1)$ trees of height $O(1)$, yielding solutions within a constant factor of the optimum. We prove that the maximum inferred consensus tree problem is NP-complete and we provide a simple fast heuristic for it, yielding solutions within one third of the optimum. We also present a more specialized polynomial-time heuristic for the maximum inferred local consensus tree problem.

Details

show
hide
Language(s): eng - English
 Dates: 1996
 Publication Status: Issued
 Pages: 14 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: Report Nr.: MPI-I-1996-1-031
BibTex Citekey: GasieniecJanssonLingasÖstlin96
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -