Simple neural-like p systems for maximal independent set selection.
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....
| Main Authors: | , |
|---|---|
| פורמט: | Journal article |
| שפה: | English |
| יצא לאור: |
2013
|
| _version_ | 1826276797464969216 |
|---|---|
| author | Xu, L Jeavons, P |
| author_facet | Xu, L Jeavons, P |
| author_sort | Xu, L |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T23:19:15Z |
| format | Journal article |
| id | oxford-uuid:682dfea7-a28f-4791-9dc6-db0c53add57a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:19:15Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | oxford-uuid:682dfea7-a28f-4791-9dc6-db0c53add57a2022-03-26T18:43:13ZSimple neural-like p systems for maximal independent set selection.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:682dfea7-a28f-4791-9dc6-db0c53add57aEnglishSymplectic Elements at Oxford2013Xu, LJeavons, PMembrane 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. |
| spellingShingle | Xu, L Jeavons, P Simple neural-like p systems for maximal independent set selection. |
| title | Simple neural-like p systems for maximal independent set selection. |
| title_full | Simple neural-like p systems for maximal independent set selection. |
| title_fullStr | Simple neural-like p systems for maximal independent set selection. |
| title_full_unstemmed | Simple neural-like p systems for maximal independent set selection. |
| title_short | Simple neural-like p systems for maximal independent set selection. |
| title_sort | simple neural like p systems for maximal independent set selection |
| work_keys_str_mv | AT xul simpleneurallikepsystemsformaximalindependentsetselection AT jeavonsp simpleneurallikepsystemsformaximalindependentsetselection |