Access Restriction

Author Frick, Markus ♦ Grohe, Martin
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2001
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword First-order logic ♦ Locality ♦ Model-checking ♦ Parameterized complexity ♦ Planar graphs ♦ Query evaluation ♦ Tree-width
Abstract 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 φ of structures that is definable in first-order logic and for each locally tree-decomposable class C of structures, there is a linear time algorithm deciding whether a given structure $\textit{A}$ ∈ C has property φ. For classes C of bounded local tree-width, we show that for every $\textit{k}$ ≥ 1 there is an algorithm solving the same problem in time $O(n^{1+(1/k)})$ (where $\textit{n}$ is the cardinality of the input structure).
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2001-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 48
Issue Number 6
Page Count 23
Starting Page 1184
Ending Page 1206

Open content in new tab

   Open content in new tab
Source: ACM Digital Library