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:
“In relation to God, we are like a thief who has burgled the house of a kindly householder and been allowed to keep some of the gold. From the point of view of the lawful owner this gold is a gift; From the point of view of the burglar it is a theft. He must go and give it back. It is the same with our existence. We have stolen a little of God’s being to make it ours. God has made us a gift of it. But we have stolen it. We must return it.”
—Simone Weil (1909–1943)
“... 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–?)