From Polynomial Time Queries to Graph Structure Theory.

We give a logical characterization of the polynomial-time properties of graphs with excluded minors: For every class C of graphs such that some graph H is not a minor of any graph in C, a property P of graphs in C is decidable in polynomial time if and only if it is definable in fixed-point logic wi...

Descripción completa

Detalles Bibliográficos

Publicado en:	Communications of the ACM Vol. 54; no. 6; pp. 104 - 113
Autor principal:	Grohe, Martin
Formato:	Artículo
Publicado:	Association for Computing Machinery Jun2011
Materias:	Polynomials Querying (Computer science) Graph theory Algorithms Set theory Computer programming
Acceso en línea:	Ver este registro en EBSCOhost