DocumentCode :
3045865
Title :
A probabilistic parameterized algorithm for vertex cover in sticker model
Author :
Chen, Zhiyun ; Qu, Huiqin ; Mingming Lu ; Zhu, Hong
Author_Institution :
Dept. of Comput. Sci., Zhejiang Univ., Hangzhou, China
fYear :
2004
fDate :
26-30 April 2004
Firstpage :
166
Abstract :
Summary form only given. We present a probabilistic parameterized algorithm for the problem of vertex cover with time complexity O(p2k), 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(2k) and polynomial time complexity O(n2), where n is the number of vertexes.
Keywords :
biocomputing; computational complexity; probability; DNA computing; polynomial time complexity; probabilistic parameterized algorithm; sticker model; Algorithm design and analysis; Annealing; Computer science; DNA computing; Information processing; Laboratories; NP-complete problem; Parallel processing; Polynomials; Space technology;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International
Print_ISBN :
0-7695-2132-0
Type :
conf
DOI :
10.1109/IPDPS.2004.1303163
Filename :
1303163
Link To Document :
بازگشت