J 2006

Matroid Tree-Width

HLINĚNÝ, Petr and Geoff WHITTLE

Basic information

Original name

Matroid Tree-Width

Name in Czech

Stromová šířka matroidů

Authors

HLINĚNÝ, Petr (203 Czech Republic, guarantor) and Geoff WHITTLE (554 New Zealand)

Edition

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

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10101 Pure mathematics

Country of publisher

United States of America

Confidentiality degree

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

References:

Impact factor

Impact factor: 0.710

RIV identification code

RIV/00216224:14330/06:00016917

Organization unit

Faculty of Informatics

UT WoS

000240627600007

Keywords in English

graph; matroid; tree-width; branch-width

Tags

Tags

International impact, Reviewed
Změněno: 16/11/2006 11:47, prof. RNDr. Petr Hliněný, Ph.D.

Abstract

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.

In Czech

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

Links

MSM0021622419, plan (intention)
Name: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1M0545, research and development project
Name: Institut Teoretické Informatiky
Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science