Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A polynomial-time algorithm for near-perfect phylogeny
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2003 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 32, no 5, 1115-1127 p.Article in journal (Refereed) Published
Abstract [en]

A parameterized version of the Steiner tree problem in phylogeny is defined, where the parameter measures the amount by which a phylogeny differs from perfection. This problem is shown to be solvable in polynomial time for any fixed value of the parameter.

Place, publisher, year, edition, pages
2003. Vol. 32, no 5, 1115-1127 p.
Keyword [en]
algorithms, computational biology, character-based methods, evolutionary trees, parsimony, perfect phylogeny, phylogeny, Steiner tree, complexity
Identifiers
URN: urn:nbn:se:kth:diva-22853DOI: 10.1137/s0097539799350839ISI: 000185629400001OAI: oai:DiVA.org:kth-22853DiVA: diva2:341551
Note
QC 20100525Available from: 2010-08-10 Created: 2010-08-10 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lagergren, Jens
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
SIAM journal on computing (Print)

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 27 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf