Skip to content
Back to outputs

On the tree-width of a graph

Research output: Contribution to journal › Article › peer-review

Standard

On the tree-width of a graph. / Chlebikova, Janka.

In: Acta Mathematica Universitatei Comenianae, Vol. 61, No. 2, 1992, p. 225-236.

Research output: Contribution to journal › Article › peer-review

Harvard

Chlebikova, J 1992, 'On the tree-width of a graph', Acta Mathematica Universitatei Comenianae, vol. 61, no. 2, pp. 225-236. <http://www.emis.de/journals/AMUC/_vol-61/_no_2/_chlebik/chlebiko.html>

APA

Chlebikova, J. (1992). On the tree-width of a graph. Acta Mathematica Universitatei Comenianae, 61(2), 225-236. http://www.emis.de/journals/AMUC/_vol-61/_no_2/_chlebik/chlebiko.html

Vancouver

Chlebikova J. On the tree-width of a graph. Acta Mathematica Universitatei Comenianae. 1992;61(2):225-236.

Author

Chlebikova, Janka. / On the tree-width of a graph. In: Acta Mathematica Universitatei Comenianae. 1992 ; Vol. 61, No. 2. pp. 225-236.

Bibtex

@article{12bdbcd547e54815a00e894221a9408c,
title = "On the tree-width of a graph",
abstract = "Robertson and Seymour introduced the concept of the tree-width of a graph. It plays an important role in their results on graph minors culminating in their proof of Wagner's conjecture. This concept seems to be interesting from the algorithmic point of view as well: many graph problems that are NP-complete in general can be polynomially solvable if graphs are constrained to have bounded tree-width [Robertson, Seymour: Graph Minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 1986] . In the present paper several equivalent definitions of tree-width are discussed and tree-width of several families of graphs is determined. ",
author = "Janka Chlebikova",
year = "1992",
language = "English",
volume = "61",
pages = "225--236",
journal = "Acta Mathematica Universitatei Comenianae",
issn = "0862-9544",
publisher = "Univerzita Komenskeho",
number = "2",

}

RIS

TY - JOUR

T1 - On the tree-width of a graph

AU - Chlebikova, Janka

PY - 1992

Y1 - 1992

N2 - Robertson and Seymour introduced the concept of the tree-width of a graph. It plays an important role in their results on graph minors culminating in their proof of Wagner's conjecture. This concept seems to be interesting from the algorithmic point of view as well: many graph problems that are NP-complete in general can be polynomially solvable if graphs are constrained to have bounded tree-width [Robertson, Seymour: Graph Minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 1986] . In the present paper several equivalent definitions of tree-width are discussed and tree-width of several families of graphs is determined.

AB - Robertson and Seymour introduced the concept of the tree-width of a graph. It plays an important role in their results on graph minors culminating in their proof of Wagner's conjecture. This concept seems to be interesting from the algorithmic point of view as well: many graph problems that are NP-complete in general can be polynomially solvable if graphs are constrained to have bounded tree-width [Robertson, Seymour: Graph Minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 1986] . In the present paper several equivalent definitions of tree-width are discussed and tree-width of several families of graphs is determined.

M3 - Article

VL - 61

SP - 225

EP - 236

JO - Acta Mathematica Universitatei Comenianae

JF - Acta Mathematica Universitatei Comenianae

SN - 0862-9544

IS - 2

ER -

ID: 1888492