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:
“Whoever has a keen eye for profits, is blind in relation to his craft.”
—Sophocles (497–406/5 B.C.)
“You know there are no secrets in America. It’s quite different in England, where people think of a secret as a shared relation between two people.”
—W.H. (Wystan Hugh)