1. UKM Learning and Research Repository
2. Master Thesis / Tesis Master
3. Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Title:	Using membrane computing for solving the minimum dominating set problem
Authors:	Ali Abdulkareem Mahmood (P65619)
Supervisor:	Ravie Chandren Muniyandi, Dr.
Keywords:	Membrane computing
Issue Date:	9-Jan-2015
Description:	Membrane systems are models of computation which are inspired by some basic features of biological membranes. In a membrane system multisets of objects are placed in the compartments defined by the membrane structure. These objects are assumed to evolve: each object can be transformed in other objects, can pass through a membrane, or can dissolve the membrane in which it is placed. A priority relation between evolution rules can be considered. The evolution rules are done in maximally parallel manner; at each step for all objects able to evolve should evolve. The minimum dominating set (MDS) problem is one of the central problems of algorithmic graph theory and has numerous applications especially in graph mining. In graph theory, a MDS for a graph G = (V, E) is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number ? (G) is the number of vertices in the smallest MDS for G. The MDS problem concerns testing whether ? (G) ? K for a given graph G and input K. The main objective of this research is to reduce the complexity time and finding the minimum size of the MDS for the undirected graphs. In this way they obtain a computing device that called P system. The P systems are parallel molecular computing models based on processing multi sets of objects in cell-like membrane structures. The ability of these systems to solve particular problems is investigated, as well as their computational power. A halting computation can accept, generate or process a number, a vector or a word, so the system globally defines (by the results of all its computations) a set of numbers or a set of vectors or a set of words. A computation device is obtained: start from initial configuration and let the system evolve. A computations halts when no further rules can be applied. The output consist of the string can be obtained by concatenating the objects which leaves the system through the membrane skin, that taken in order they are sent out. The main idea behind this methodology is the need to find optimal solution and improving the time complexity for the MDS problem, a goal achieved by the variant of membrane computing model called P systems with active membrane is used to improve the time complexity of MDS. The rules of P systems with active membrane are utilized to solve the MDS problem, and the result is compared with the tile-self-assembly system and an improved integer linear programming. This method implements the MDS problem in linear time (2*n+m+4 steps). Membrane computing with its capacity for parallel processing is efficient compared to tile-self-assembly system and an improved integer linear programming to implement the MDS.,Master/Sarjana
Pages:	87
Publisher:	UKM, Bangi
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.