A Probabilistic Parameterized Algorithm for Vertex Cover in Sticker Model

	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 Zhiyun Chen Articles by Huiqin Qu Articles by Mingming Lu Articles by Hong Zhu

18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 6

Santa Fe, New Mexico

April 26-April 30

ISBN: 0-7695-2132-0

	ASCII Text	x
	Zhiyun Chen, Huiqin Qu, Mingming Lu, Hong Zhu, "A Probabilistic Parameterized Algorithm for Vertex Cover in Sticker Model," Parallel and Distributed Processing Symposium, International, vol. 7, pp. 166b, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 6, 2004.

	BibTex	x
	@article{ 10.1109/IPDPS.2004.1303163, author = {Zhiyun Chen and Huiqin Qu and Mingming Lu and Hong Zhu}, title = {A Probabilistic Parameterized Algorithm for Vertex Cover in Sticker Model}, journal ={Parallel and Distributed Processing Symposium, International}, volume = {7}, year = {2004}, isbn = {0-7695-2132-0}, pages = {166b}, doi = {http://doi.ieeecomputersociety.org/10.1109/IPDPS.2004.1303163}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel and Distributed Processing Symposium, International TI - A Probabilistic Parameterized Algorithm for Vertex Cover in Sticker Model SN - 0-7695-2132-0 SP EP A1 - Zhiyun Chen, A1 - Huiqin Qu, A1 - Mingming Lu, A1 - Hong Zhu, PY - 2004 KW - null VL - 7 JA - Parallel and Distributed Processing Symposium, International ER -

Zhiyun Chen, Zhejiang University

Huiqin Qu, Fudan University

Mingming Lu, Fudan University

Hong Zhu, Fudan University

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2004.1303163

We present a probabilistic parameterized algorithm for the problem of vertex cover with time complexity 0(p2^k), where k is a parameter of the given instance, and p is a polynomial function on the input size. Furthermore, we implement this algorithm within sticker model by DNA computing, with space complexity O(2^k) and polynomial time complexity O(n^2), where n is the number of vertexes.

Citation:

Zhiyun Chen, Huiqin Qu, Mingming Lu, Hong Zhu, "A Probabilistic Parameterized Algorithm for Vertex Cover in Sticker Model," ipdps, vol. 7, pp.166b, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 6, 2004

Peer Review Notice | Give Us Feedback

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