Matroidy v teoretické informatice

Kód výsledku v IS VaVaI

RIV/61989100:27240/05:00012172 - isvavai.cz

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.

Druh

A - Audiovizuální tvorba

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

GA201/05/0050: Strukturální vlastnosti a algoritmická složitost diskrétních problémů

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ů

ISBN

—

Místo vydání

Praha

Název nakladatele resp. objednatele

MFF UK

Verze

—

Identifikační číslo nosiče

—