A Probabilistic Parameterized Algorithm for Vertex Cover in Sticker Model

Santa Fe, New Mexico April 26-April 30

DOI Bookmark:

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

18th International Parallel and Distr ...

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

	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

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.