Publication details
Decomposition width of matroids
| Authors | |
|---|---|
| Year of publication | 2012 |
| Type | Article in Periodical |
| Magazine / Source | Discrete Applied Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.dam.2011.03.016 |
| Keywords | Matroids; Matroid algorithms; Branch-width; Algorithmic metatheorems |
| Description | Hlineny [P. Hlineny, 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. (C) 2011 Elsevier B.V. All rights reserved. |