Decomposition width - a new width parameter for matroids

Details Decomposition width - a new width parameter for matroids Decomposition width - a new width parameter for matroids

2009-04-17

arxiv.org/abs/0904.2785v1

Computer Science

Discrete Mathematics

Scientific paper

We introduce a new width parameter for matroids called decomposition width and prove that every matroid property expressible in the monadic second order logic can be computed in linear time for matroids with bounded decomposition width if their decomposition is given. Since decompositions of small width for our new notion can be computed in polynomial time for matroids of bounded branch-width represented over finite fields, our results include recent algorithmic results of Hlineny [J. Combin. Theory Ser. B 96 (2006), 325-351] in this area and extend his results to matroids not necessarily representable over finite fields.

Affiliated with

Also associated with

No associations

Rating

Decomposition width - a new width parameter for 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 Decomposition width - a new width parameter for matroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decomposition width - a new width parameter for matroids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-545225