A Linear-time Tissue P System Based Solution for the 3-coloring Problem

被引：26

作者：

Diaz-Pernil, Daniel ^{[1
]}

Gutierrez-Naranjo, Miguel A. ^{[1
]}

Perez-Jimenez, Mario J. ^{[1
]}

Riscos-Nunez, Agustin ^{[1
]}

机构：

[1] Univ Seville, Dpto Ciencias Computac & Inteligencia Artificial, Res Grp Nat Comp, Seville, Spain

来源：

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE | 2007年 / 171卷 / 02期

关键词：

Membrane Computing; Tissue P Systems; cell division; 3-coloring problem;

D O I：

10.1016/j.entcs.2007.05.009

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the literature, several examples of the efficiency of cell-like P systems regarding the solution of NP-complete problems in polynomial time can be found (obviously, trading space for time). Recently, different new models of tissue-like P systems have received important 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.

引用

页码：81 / 93

页数：13

共 29 条

[1]

Alberts B., 2007, MOL BIOL CELL

[2]

Alhazov A, 2005, LECT NOTES COMPUT SC, V3572, P100

[3] EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING [J].

APPEL, K ;

HAKEN, W .

ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :429-490

[4] EVERY PLANAR MAP IS 4 COLORABLE .2. REDUCIBILITY [J].

APPEL, K ;

HAKEN, W ;

KOCH, J .

ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :491-567

[5] Cell communication in tissue P systems: Universality results [J].

Bernardini, F ;

Gheorghe, M .

SOFT COMPUTING, 2005, 9 (09) :640-649

[6]

Cardelli L, 2005, LECT NOTES COMPUT SC, V3082, P257

[7] Tissue P systems with channel states [J].

Freund, R ;

Paun, G ;

Pérez-Jiménez, MJ .

THEORETICAL COMPUTER SCIENCE, 2005, 330 (01) :101-116

[8]

Frisco P, 2003, LECT NOTES COMPUT SC, V2597, P288

[9]

Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness

[10]

Gutierrez-Naranjo MA, 2006, LECT NOTES COMPUT SC, V3850, P241

← 1 2 3 →