A Polynomial Algorithm for the Minimum Quartet Inconsistency Problem with O(n) Quartet Errors

Stanford, California August 08-August 11

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CSBW.2005.14

2005 IEEE Computational Systems Bioin ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Gang Wu Articles by Jia-Huai You Articles by Guohui Lin

	ASCII Text	x
	Gang Wu, Jia-Huai You, Guohui Lin, "A Polynomial Algorithm for the Minimum Quartet Inconsistency Problem with O(n) Quartet Errors," 2005 IEEE Computational Systems Bioinformatics Conference - Workshops, pp. 55-56, 2005 IEEE Computational Systems Bioinformatics Conference - Workshops (CSBW'05), 2005.

	BibTex	x
	@article{ 10.1109/CSBW.2005.14, author = {Gang Wu and Jia-Huai You and Guohui Lin}, title = {A Polynomial Algorithm for the Minimum Quartet Inconsistency Problem with O(n) Quartet Errors}, journal ={2005 IEEE Computational Systems Bioinformatics Conference - Workshops}, volume = {0}, year = {2005}, isbn = {0-7695-2442-7}, pages = {55-56}, doi = {http://doi.ieeecomputersociety.org/10.1109/CSBW.2005.14}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - 2005 IEEE Computational Systems Bioinformatics Conference - Workshops TI - A Polynomial Algorithm for the Minimum Quartet Inconsistency Problem with O(n) Quartet Errors SN - 0-7695-2442-7 SP55 EP56 A1 - Gang Wu, A1 - Jia-Huai You, A1 - Guohui Lin, PY - 2005 KW - null VL - 0 JA - 2005 IEEE Computational Systems Bioinformatics Conference - Workshops ER -

Gang Wu, University of Alberta

Jia-Huai You, University of Alberta

Guohui Lin, University of Alberta

We show that for the Minimum Quartet Inconsistency problem, if the number of quartet errors is O(n), where n is the number of taxa under consideration, then it can be solved in polynomial time. This improves the previously best algorithmic result saying that if the number of quartet errors is at most (n - 3)/2 then the problem can be solved in polynomial time.

Citation:

Gang Wu, Jia-Huai You, Guohui Lin, "A Polynomial Algorithm for the Minimum Quartet Inconsistency Problem with O(n) Quartet Errors," csbw, pp.55-56, 2005 IEEE Computational Systems Bioinformatics Conference - Workshops (CSBW'05), 2005

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.