Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Computing Representations of Matroids of Bounded Branch-Width
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
For every
k
≥ 1 and two finite fields
${\mathbb F}$
and
${\mathbb F}'$
, we design a polynomial-time algorithm that given a matroid
${\mathcal M}$
of branch-width at most
k
represented over
${\mathbb F}$
decides whether
${\mathcal M}$
is representable over
${\mathbb F}'$
and if so, it computes a representation of
${\mathcal M}$
over
${\mathbb F}'$
. The algorithm also counts the number of non-isomorphic representations of
${\mathcal M}$
over
${\mathbb F}'$
. Moreover, it can be modified to list all such non-isomorphic representations.