Width parameters of graphs and matroids

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F05%3A00012174" target="_blank" >RIV/61989100:27240/05:00012174 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Width parameters of graphs and matroids

Popis výsledku v původním jazyce

We will review some known "width" parameters of graphs, and relate them to matroids. In particular, we use matroids to introduce a vertex-free definition of graph tree-width, and we show how matroid branch-width is related with decidability of MSO theories of both matroids and graphs (cf. rank-width).

Název v anglickém jazyce

Width parameters of graphs and matroids

Popis výsledku anglicky

We will review some known "width" parameters of graphs, and relate them to matroids. In particular, we use matroids to introduce a vertex-free definition of graph tree-width, and we show how matroid branch-width is related with decidability of MSO theories of both matroids and graphs (cf. rank-width).

Druh

D - Stať ve sborníku

CEP obor

BD - Teorie informace

OECD FORD obor

—

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ů

Název statě ve sborníku

Exact Algorithms and Fixed-Parameter Tractability

ISBN

1862 - 4405

ISSN

—

e-ISSN

—

Počet stran výsledku

6

Strana od-do

6-12

Název nakladatele

Dagstuhl

Místo vydání

Wadern

Místo konání akce

Dagstuhl, Germany

Datum konání akce

23. 7. 2005

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—