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:
“... 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–?)
“Every word was once a poem. Every new relation is a new word.”
—Ralph Waldo Emerson (1803–1882)