Deciding first-order properties of locally tree-decomposable structures

Details Deciding first-order properties of locally tree-decomposable structures Deciding first-order properties of locally tree-decomposable structures

2000-04-17

arxiv.org/abs/cs/0004007v1

Computer Science

Data Structures and Algorithms

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

Deciding first-order properties of locally tree-decomposable structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deciding first-order properties of locally tree-decomposable structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deciding first-order properties of locally tree-decomposable structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-589613