Matroidy v teoretické informatice

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F05%3A00012172" target="_blank" >RIV/61989100:27240/05:00012172 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
čeština
Název v původním jazyce
Matroidy v teoretické informatice
Popis výsledku v původním jazyce
Matroidy jsou kombinatorické struktury, které široce zobecňují jak grafy, tak i třeba (konečné) geometrie. Pomineme-li algoritmy v kombinatorické optimalizaci [Edmonds a další], matroidy nejsou příliš rozšířeny v teoretické informatice. V naší přednášcebychom rádi ukázali přehled několika poměrně nových výsledků ukazujících užitečnost matroidů v informatice. Centrálním pojmem naší prezentace je větvená a stromová šířka ve zobecnění na matroidy. (Pojem stromové šířky matroidu nám mimo jiné dává i zcelanový, "bezvrcholový", pohled na klasickou stromovou šířku grafů.) V úzké návaznosti bychom shrnuli naše nedávné výsledky o rozhodnutelnosti MSO teorií na reprezentovatelných matroidech a nastínili možné směry budoucích zobecnění na abstraktní matroidy. Závěrem bychom využili příležitost ke krátké prezentaci nového online přístupu k našemu programu Macek pro strukturální výpočty s matroidy. Část prezentovaných výsledků byla dosažena ve spolupráci s D.Seesem a s G.Whittlem.
Název v anglickém jazyce
Matroids in theoretical CS
Popis výsledku anglicky
Matroids are combinatorial structures extending the notion of graphs. We study mainly width parameters on matroids, like branch-width or tree-width.

Projekt
<a href="/cs/project/GA201%2F05%2F0050" target="_blank" >GA201/05/0050: Strukturální vlastnosti a algoritmická složitost diskrétních problémů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2005
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)