Combinatorial Generation of Matroid Representations: Theory and Practice

HLINĚNÝ, Petr. Combinatorial Generation of Matroid Representations: Theory and Practice. In Innovative Applications of Information Technology for the Developing World. Singapore: World Scientific Publishing, 2007, s. 3-7. ISBN 978-1-86094-827-5.

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í

Singapore, Innovative Applications of Information Technology for the Developing World, od s. 3-7, 5 s. 2007

Nakladatel

World Scientific Publishing

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Singapur

Utajení

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

Odkazy

conference

Kód RIV

RIV/00216224:14330/07:00021396

Organizační jednotka

Fakulta informatiky

ISBN

978-1-86094-827-5

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

MSM0021622419, záměr	Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky