Login New user?  
01-Applied Mathematics & Information Sciences
An International Journal
               
 
 
 
 
 
 
 
 
 
 
 

Content
 

Volumes > Volume 8 > No. 1

 
   

Parallel Solution to the Dominating Set Problem by Tile Assembly System

PP: 345-349
Author(s)
Hongjiang Zheng, Yufang Huang, Jianhua Xiao, Jian Liu, Tao Song,
Abstract
The dominating set problem is a well known NP hard problem. It means that as the instance size grows, they quickly become impossible to solve on traditional digital computers. Tile assembly model has been demonstrated as a highly distributed parallel model of computation. Algorithmic tile assembly has been proved to be Turing-universal. This paper proposes a tile assembly system for the dominating set problem. It only needsQ(mn) tile types to solve such a complex problem in the timeQ(m+n) where n and m are the number of vertices and edges of the given graph, respectively.

  Home   About us   News   Journals   Conferences Contact us Copyright naturalspublishing.com. All Rights Reserved