|
|
 |
| |
|
|
|
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. |
|
|
|
|
|
|
|
