•  
  •  
 

Author Country (or Countries)

P.R. China

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.

Suggested Reviewers

N/A

Digital Object Identifier (DOI)

http://dx.doi.org/10.18576/amis/080143

Share

COinS