Informace o publikaci
Decomposition width of matroids
| Autoři | |
|---|---|
| Rok publikování | 2012 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Discrete Applied Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.dam.2011.03.016 |
| Klíčová slova | Matroids; Matroid algorithms; Branch-width; Algorithmic metatheorems |
| Popis | 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. |