Evaluating non-deterministic signal machine relative complexity: a case study on dominating set problem
by Sahar Ardalan; Sama Goliaei; Ayaz Isazadeh
International Journal of Innovative Computing and Applications (IJICA), Vol. 11, No. 1, 2020

Abstract: Signal machine is an abstract geometrical model of computation, which can be viewed as a continuous space and time generalisation of cellular automata. Almost all studies that have been made are about deterministic signal machines. In spite of few studies that have been made on non-deterministic signal machines, the present paper shows their high efficiency in solving problems using a well-known combinatorial problem. We provide a method to solve the graph dominating set problem using non-deterministic signal machines. First, we show how to design a signal machine for each specific instance of the dominating set problem. Then, we propose a signal machine which solves the dominating set problem for any instance of the problem, and show how to reduce the space complexity of solution using non-determinism.

Online publication date: Mon, 24-Feb-2020

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Innovative Computing and Applications (IJICA):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com