Deciding first-order properties of locally tree-decomposable structures
| dc.creator | Frick, Markus | |
| dc.creator | Grohe, Martin | |
| dc.date | 2000-04-17 | |
| dc.date.accessioned | 2026-07-07T03:16:09Z | |
| dc.date.available | 2026-07-07T03:16:09Z | |
| dc.description | We introduce the concept of a class of graphs, or more generally, relational structures, being locally tree-decomposable. There are numerous examples of locally tree-decomposable classes, among them the class of planar graphs and all classes of bounded valence or of bounded tree-width. We also consider a slightly more general concept of a class of structures having bounded local tree-width. We show that for each property P of structures that is definable in first-order logic and for each locally tree-decomposable class C of graphs, there is a linear time algorithm deciding whether a given structure A in C has property P. For classes C of bounded local tree-width, we show that for every k\ge 1 there is an algorithm that solves the same problem in time O(n^{1+(1/k)}) (where n is the cardinality of the input structure). | |
| dc.identifier | https://arxiv.org/abs/cs/0004007 | |
| dc.identifier | http://arxiv.org/abs/cs/0004007 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30245 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | Databases | |
| dc.subject | F.2.2; G.2.2; H.2.4; F.1.3 | |
| dc.title | Deciding first-order properties of locally tree-decomposable structures | |
| dc.type | text |