Using membrane computing for solving the minimum dominating set problem

Ali Abdulkareem Mahmood (P65619)

Please use this identifier to cite or link to this item: https://ptsldigital.ukm.my/jspui/handle/123456789/476227

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Ravie Chandren Muniyandi, Dr.
dc.contributor.author	Ali Abdulkareem Mahmood (P65619)
dc.date.accessioned	2023-10-06T09:14:54Z	-
dc.date.available	2023-10-06T09:14:54Z	-
dc.date.issued	2015-01-09
dc.identifier.other	ukmvital:76523
dc.identifier.uri	https://ptsldigital.ukm.my/jspui/handle/123456789/476227	-
dc.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
dc.language.iso	eng
dc.publisher	UKM, Bangi
dc.relation	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat
dc.rights	UKM
dc.subject	Membrane computing
dc.title	Using membrane computing for solving the minimum dominating set problem
dc.type	theses
dc.format.pages	87
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Files in This Item:

File	Description	Size	Format
ukmvital_76523+SOURCE1+SOURCE1.0.PDF Restricted Access		403.55 kB	Adobe PDF	View/Open

Show simple item record Recommend this item