title: Simple neural-like p systems for maximal independent set selection.
abstract: Membrane systems (P systems) are distributed computing models inspired by living cells where a collection of processors jointly achieves a computing task. The problem of maximal independent set (MIS) selection in a graph is to choose a set of nonadjacent nodes to which no further nodes can be added. In this letter, we design a class of simple neural-like P systems to solve the MIS selection problem efficiently in a distributed way. This new class of systems possesses two features that are attractive for both distributed computing and membrane computing: first, the individual processors do not need any information about the overall size of the graph; second, they communicate using only one-bit messages.
authors.affiliation: Department of Computer Science, University of Oxford, Oxford OX1 3QD, UK. lei.xu@cs.ox.ac.uk
authors.forename: Lei
authors.initials: L
authors.lastname: Xu
authors.forename: Peter
authors.initials: P
authors.lastname: Jeavons
mesh_terms: D001921:Brain / Q000166:cytology; D003198:Computer Simulation; D006801:Humans; D008959:Models, Neurological; D016571:Neural Networks, Computer; D009474:Neurons / Q000502:physiology*; D011336:Probability; D012718:Set, Psychology