Recognizing Circular Decomposable Metrics
- 1 January 1997
- journal article
- research article
- Published by Mary Ann Liebert Inc in Journal of Computational Biology
- Vol. 4 (2) , 157-162
- https://doi.org/10.1089/cmb.1997.4.157
Abstract
Circular decomposable metrics (CDMs) have been used in phylogenetic studies. The fastest algorithm for recognizing a CDM runs in time 0(n5), given an n × n table of pairwise distances. We give an 0(n2) time algorithm for this problem.Keywords
This publication has 3 references indexed in Scilit:
- Split decomposition: a technique to analyze viral evolution.Proceedings of the National Academy of Sciences, 1993
- A canonical decomposition theory for metrics on a finite setAdvances in Mathematics, 1992
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976