A uniform family of tissue P systems with protein on cells solving 3-coloring in linear time

DOI10.1007/S11047-016-9590-1MaRDI QIDQ6061997zbMATH OpenOpenAlexFDO

Authors A. Hepzibah Christinal, Daniel Díaz-Pernil, T. Mathu

Publication date 30 November 2023

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11047-016-9590-1

zbMATH Keywords

3-coloring problemmembrane computingprotein on cellstissue P-system

Mathematics Subject Classification ID

Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A uniform family of tissue P systems with protein on cells solving 3-coloring in linear time
• A linear-time tissue P system based solution for the 3-coloring problem
• A uniform family of tissue P systems with cell division solving 3-COL in a linear time
• A uniform solution to the independent set problem through tissue P systems with cell separation
• Solving the 3-COL problem by using tissue P systems without environment and proteins on cells
• A time-free uniform solution to subset sum problem by tissue P systems with cell division
• Tissue P systems with cell separation: upper bound by PSPACE
• Enumerating colorings, tensions and flows in cell complexes
• A tissue P systems based uniform solution to tripartite matching problem

Cites work

• 3-Col problem modelling using simple kernel P systems
• A polynomial complexity class in P systems using membrane division
• A uniform family of tissue P systems with cell division solving 3-COL in a linear time
• Cell communication in tissue \(P\) systems: universality results
• Computing with membranes
• Developments in Language Theory
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1951592 (Why is no real title available?)
• scientific article; zbMATH DE number 2089984 (Why is no real title available?)
• Membrane computing. An introduction.
• Tissue P systems with channel states
• Tissue P systems.

Cited in

(2)

• A time-free uniform solution to subset sum problem by tissue P systems with cell division
• Weighted spiking neural P systems with polarizations and anti-spikes

This page was built for publication: A uniform family of tissue P systems with protein on cells solving 3-coloring in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6061997)