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 difference between objective and subjective extension is one of relation to a context solely.”
—William James (1842–1910)
“Whoever has a keen eye for profits, is blind in relation to his craft.”
—Sophocles (497–406/5 B.C.)