J 2006

Matroid Tree-Width

HLINĚNÝ, Petr a Geoff WHITTLE

Základní údaje

Originální název

Matroid Tree-Width

Název česky

Stromová šířka matroidů

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant) a Geoff WHITTLE (554 Nový Zéland)

Vydání

European Journal of Combinatorics, Elsevier, 2006, 0195-6698

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

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

Odkazy

Impakt faktor

Impact factor: 0.710

Kód RIV

RIV/00216224:14330/06:00016917

Organizační jednotka

Fakulta informatiky

UT WoS

000240627600007

Klíčová slova anglicky

graph; matroid; tree-width; branch-width

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 16. 11. 2006 11:47, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

ORIG CZ

V originále

We show that the tree-width of a graph can be defined without reference to graph vertices, and hence the notion of tree-width can be naturally extended to matroids. (This extension was inspired by an original unpublished idea of Jim Geelen.) We prove that the tree-width of a graphic matroid is equal to that of its underlying graph. Furthermore, we extend the well-known relation between the branch-width and the tree-width of a graph to all matroids.

Česky

Ukážeme, jak klasickou tree-width grafů definovat bez odkazu na vrcholy. Naše nová definice dává tree-width také pro matroidy.

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