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:
“Any relation to the land, the habit of tilling it, or mining it, or even hunting on it, generates the feeling of patriotism. He who keeps shop on it, or he who merely uses it as a support to his desk and ledger, or to his manufactory, values it less.”
—Ralph Waldo Emerson (1803–1882)
“The difference between objective and subjective extension is one of relation to a context solely.”
—William James (1842–1910)