کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420193 | 683902 | 2012 | 11 صفحه PDF | دانلود رایگان |

Hliněný [P. Hliněný, Branch-width, parse trees, and monadic second-order logic for matroids, J. Combin. Theory Ser. B 96 (2006), 325–351] showed that every matroid property expressible in the monadic second-order logic can be decided in linear time for matroids with bounded branch-width that are represented over finite fields. To be able to extend these algorithmic results to matroids not representable over finite fields, we introduce a new width parameter for matroids, the decomposition width, and show that every matroid property expressible in the monadic second-order logic can be computed in linear time for matroids given by a decomposition with bounded width. We also relate the decomposition width to matroid branch-width and discuss implications of our results with respect to known algorithms.
Journal: Discrete Applied Mathematics - Volume 160, Issue 6, April 2012, Pages 913–923