کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420193 683902 2012 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Decomposition width of matroids
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Decomposition width of matroids
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 6, April 2012, Pages 913–923
نویسندگان
,