Computing representations of matroids of bounded branch-width

KRÁĽ, Daniel. Computing representations of matroids of bounded branch-width. Stacs 2007, Proceedings. BERLIN: SPRINGER-VERLAG BERLIN, 2007, roč. 4393, s. 224-235. ISSN 0302-9743.

Základní údaje

Originální název

Computing representations of matroids of bounded branch-width

Autoři

KRÁĽ, Daniel

Vydání

Stacs 2007, Proceedings, BERLIN, SPRINGER-VERLAG BERLIN, 2007, 0302-9743

---

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í

Označené pro přenos do RIV

Ne

UT WoS

000245503800020

---

Anotace

V originále

For every k >= I and two finite fields F and F', we design a polynomial-time algorithm that given a matroid M of branch-width at most k represented over F decides whether M is representable over F' and if so, it computes a representation of M over F'. The algorithm also counts the number of non-isomorphic representations of M over F'. Moreover, it can be modified to list all such non-isomorphic representations.