Combinatorial Generation of Matroid Representations: Theory and Practice
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F07%3A00021396" target="_blank" >RIV/00216224:14330/07:00021396 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Combinatorial Generation of Matroid Representations: Theory and Practice
Original language description
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.
Czech name
Kombinatorické generování reprezentací matroidů: teorie a praxe
Czech description
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.
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Innovative Applications of Information Technology for the Developing World
ISBN
978-1-86094-827-5
ISSN
—
e-ISSN
—
Number of pages
5
Pages from-to
3-7
Publisher name
World Scientific Publishing
Place of publication
Singapore
Event location
Kathmandu, Nepal
Event date
Jan 1, 2005
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—