Relation To Treewidth
Branch-decompositions of graphs are closely related to tree decompositions, and branch-width is closely related to tree-width: the two quantities are always within a constant factor of each other. In particular, in the paper in which they introduced branch-width, Neil Robertson and Paul Seymour showed that for a graph G with tree-width k and branchwidth b > 1,
Read more about this topic: Branch-decomposition
Famous quotes containing the words relation to and/or relation:
“The proper study of mankind is man in his relation to his deity.”
—D.H. (David Herbert)
“... a worker was seldom so much annoyed by what he got as by what he got in relation to his fellow workers.”
—Mary Barnett Gilson (1877–?)