Decomposition width of matroids

KRÁĽ, Daniel. Decomposition width of matroids. Discrete Applied Mathematics. AMSTERDAM: Elsevier B.V., 2012, roč. 160, č. 6, s. 913-923. ISSN 0166-218X. Dostupné z: https://doi.org/10.1016/j.dam.2011.03.016.

Základní údaje

Originální název

Decomposition width of matroids

Autoři

KRÁĽ, Daniel

Vydání

Discrete Applied Mathematics, AMSTERDAM, Elsevier B.V. 2012, 0166-218X

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.718

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1016/j.dam.2011.03.016

UT WoS

000302981900017

Klíčová slova anglicky

Matroids; Matroid algorithms; Branch-width; Algorithmic metatheorems

---

Anotace

V originále

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.