Time-free solution to Hamilton path problems using P systems with d-division

DOI10.1155/2013/975798MaRDI QIDQ1791419zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tao Song, Xun Wang, Hongjiang Zheng

Publication date 10 October 2018

Published in Journal of Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2013/975798

zbMATH Keywords

Hamiltonian path problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Review text

Summary: P systems with \(d\)-division are a particular class of distributed and parallel computing models investigated in membrane computing, which are inspired from the budding behavior of Baker's yeast (a cell can generate several cells in one reproducing cycle). In previous works, such systems can theoretically generate exponential working space in linear time and thus provide a way to solve computational hard problems in polynomial time by a space-time tradeoff, where the precise execution time of each evolution rule, one time unit, plays a crucial role. However, the restriction that each rule has a precise same execution time does not coincide with the biological fact, since the execution time of biochemical reactions can vary because of external uncontrollable conditions. In this work, we consider timed P systems with \(d\)-division by adding a time mapping to the rules to specify the execution time for each rule, as well as the efficiency of the systems. As a result, a time-free solution to Hamiltonian path problem (HPP) is obtained by a family of such systems (constructed in a uniform way), that is, the execution time of the rules (specified by different time mappings) has no influence on the correctness of the solution.

Recommendations

• The Hamiltonian problem and \(t\)-path traceable graphs
• A successful algorithm for solving directed Hamiltonian path problems
• A simple linear expected time algorithm for finding a Hamilton path
• Approximation algorithms for multiple terminal, Hamiltonian path problems
• A successful algorithm for the undirected Hamiltonian path problem
• New solutions for disjoint paths in P systems
• On the complexity of hamiltonian path and cycle problems in certain classes of digraphs
• The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems

Cited in

(1)

• Computational efficiency and universality of timed P systems with membrane creation

This page was built for publication: Time-free solution to Hamilton path problems using P systems with \(d\)-division

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