A uniform family of tissue P systems with cell division solving 3-COL in a linear time

被引：52
作者：
Diaz-Pernil, Daniel [1 ]
Gutierrez-Naranjo, Miguel A. [1 ]
Perez-Jimenez, Mario J. [1 ]
Riscos-Nunez, Agustin [1 ]
机构：
[1] Univ Seville, Res Grp Nat Comp, Seville, Spain
来源：
THEORETICAL COMPUTER SCIENCE | 2008年 / 404卷 / 1-2期
关键词：
membrane computing; tissue P systems; cell division; 3-coloring problem;
D O I：
10.1016/j.tcs.2008.04.005
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Several examples of the efficiency of cell-like P systems regarding the solution of NP-complete problems in polynomial time can be found in the literature(obviously, trading space for time). Recently, different new models of tissue-like P systems have received much attention from the scientific community. In this paper we present a linear-time solution to an NP-complete problem from graph theory, the 3-coloring problem, and we discuss the suitability of tissue-like P systems as a framework to address the efficient solution to intractable problems. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码：76 / 87
页数：12
相关论文
共 28 条
  • [1] Alberts B., 2002, Molecular Biology of The Cell, V4th
  • [2] Alhazov A, 2005, LECT NOTES COMPUT SC, V3572, P100
  • [3] EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING
    APPEL, K
    HAKEN, W
    [J]. ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) : 429 - 490
  • [4] EVERY PLANAR MAP IS 4 COLORABLE .2. REDUCIBILITY
    APPEL, K
    HAKEN, W
    KOCH, J
    [J]. ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) : 491 - 567
  • [5] Cell communication in tissue P systems: Universality results
    Bernardini, F
    Gheorghe, M
    [J]. SOFT COMPUTING, 2005, 9 (09) : 640 - 649
  • [6] Cardelli L, 2005, LECT NOTES COMPUT SC, V3082, P257
  • [7] Tissue P systems with channel states
    Freund, R
    Paun, G
    Pérez-Jiménez, MJ
    [J]. THEORETICAL COMPUTER SCIENCE, 2005, 330 (01) : 101 - 116
  • [8] Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
  • [9] Gutiérrez-Naranjo MA, 2006, LECT NOTES COMPUT SC, V3850, P241
  • [10] Ionescu M, 2006, FUND INFORM, V71, P279
123