Deciding first order logic properties of matroids

Details Deciding first order logic properties of matroids Deciding first order logic properties of matroids

2011-08-27

arxiv.org/abs/1108.5457v1

Computer Science

Data Structures and Algorithms

Scientific paper

Frick and Grohe [J. ACM 48 (2006), 1184-1206] introduced a notion of graph classes with locally bounded tree-width and established that every first order logic property can be decided in almost linear time in such a graph class. Here, we introduce an analogous notion for matroids (locally bounded branch-width) and show the existence of a fixed parameter algorithm for first order logic properties in classes of regular matroids with locally bounded branch-width. To obtain this result, we show that the problem of deciding the existence of a circuit of length at most k containing two given elements is fixed parameter tractable for regular matroids.

Affiliated with

Also associated with

No associations

Rating

Deciding first order logic properties of matroids 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 logic properties of matroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deciding first order logic properties of matroids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-614095