J 2012

Deciding First Order Properties of Matroids

GAVENCIAK, T; Daniel KRÁĽ a SI OUM

Základní údaje

Originální název

Deciding First Order Properties of Matroids

Autoři

GAVENCIAK, T; Daniel KRÁĽ a SI OUM

Vydání

AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012, PT II, BERLIN, SPRINGER-VERLAG BERLIN, 2012, 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í

UT WoS

000342761300024
Změněno: 6. 11. 2020 09:14, Mgr. Darina Boukalová

Anotace

V originále

Frick and Grohe [J. ACM 48 (2006), 1184-1206] introduced a notion of graph classes with locally bounded tree-width and established that every first order property can be decided in almost linear time in such a graph class. Here, we introduce an analogous notion for matroids (locally bounded branch-width) and show the existence of a fixed parameter algorithm for first order properties in classes of regular matroids with locally bounded branch-width. To obtain this result, we show that the problem of deciding the existence of a circuit of length at most k containing two given elements is fixed parameter tractable for regular matroids.