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...
| Publicado en: | Communications of the ACM Vol. 54; no. 6; pp. 104 - 113 |
|---|---|
| Autor principal: | |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Jun2011
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=63231743&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 63231743 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Jun2011 vid: 54 iid: 6 pid: 68 pub: Association for Computing Machinery artinfo: ui: 63231743 10.1145/1953122.1953150 ppf: 104 ppct: 9 formats: tig: atl: From Polynomial Time Queries to Graph Structure Theory. aug: au: Grohe, Martin affil: Humboldt-Universität Berlin, Germany. su: Polynomials Querying (Computer science) Graph theory Algorithms Set theory Computer programming sug: subj: Polynomials Querying (Computer science) Graph theory Algorithms Set theory Computer programming ab: 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 with counting. Furthermore, we prove that for every class C of graphs with excluded minors there is a κ such that a simple combinatorial algorithm, namely "the κ-dimensional Weisfeiler--Lehman algorithm," decides isomorphism of graphs in C in polynomial time. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2011 holdings: @attributes: islocal: N |
|---|