Combinatorial Generation of Matroid Representations: Theory and Practice

HLINĚNÝ, Petr. Combinatorial Generation of Matroid Representations: Theory and Practice. Acta Universitatis Matthiae Belii, Series Mathematics. Banska Bystrica, Slovakia: Matej Bel University, 2006, roč. 12, č. 1, s. 31-41.

Základní údaje

Originální název

Combinatorial Generation of Matroid Representations: Theory and Practice

Název česky

Kombinatorické generování reprezentací matroidů: teorie a praxe

Autoři

HLINĚNÝ, Petr ORCID

Vydání

Acta Universitatis Matthiae Belii, Series Mathematics, Banska Bystrica, Slovakia, Matej Bel University, 2006

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Velká Británie a Severní Irsko

Utajení

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

Odkazy

URL

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

representable matroid; exhaustive generation

Štítky

exhaustive generation, representable matroid

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Matroids (also called combinatorial geometries) present a strong combinatorial generalization of graphs and matrices. Unlike isomorph-free generation of graphs, which has been extensively studied both from theoretical and practical points of view, not much research has been done so far about matroid generation. Perhaps the main problem with matroid generation lies in a very complex internal structure of a matroid. That is why we focus on generation of suitable matroid representations, and we outline a way how to exhaustively generate matroid representations over finite fields in reasonable computing time. In particular, we extend here some enumeration results on binary (over the binary field) combinatorial geometries by Kingan et al.

Česky

Matroidy (jinak kombinatorické geometrie) představují silné zobecnění grafů a matic. Na rozdíl od neisomorfního generování grafů, které bylo intenzivně studováno, o generování matroidů toho dosud moc známo není. Asi hlavním problémem je velmi složitá vnitřní struktura matroidů. Proto se zaměřujeme na generování vhodných reprezentací matroidů a ukazujeme, jak poměrně efetivně generovat všechny reprezentace malých matroidů nad konečnými tělesy. Mimo jiné rozšíříme některé enumerční výsledky o binárních matroidech získané Kingan a spol.

---

Návaznosti

GA201/05/0050, projekt VaV	Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky