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

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	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

2005 IEEE Computational Systems Bioinformatics Conference - Workshops (CSBW'05)

Stanford, California

August 08-August 11

ISBN: 0-7695-2442-7

	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

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

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.