Informace o publikaci

Decomposition width of matroids

Autoři

KRÁĽ Daniel

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.

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info