Definition & Meaning | English word BRANCHWIDTH

Definitions of BRANCHWIDTH

1. (maths) The minimum width of a branch-decomposition.

Examples of Using BRANCHWIDTH in a Sentence

• Branch-decomposition, a hierarchical clustering of the edges of a graph, and branchwidth, a graph parameter defined from these decompositions.
• Indeed, a graph has treewidth at most 2 if and only if it has branchwidth at most 2, if and only if every biconnected component is a series–parallel graph.
• As with treewidth, branchwidth can be used as the basis of dynamic programming algorithms for many NP-hard optimization problems, using an amount of time that is exponential in the width of the input graph or matroid.
• Branchwidth is an important component of attempts to extend the theory of graph minors to matroids: although treewidth can also be generalized to matroids, and plays a bigger role than branchwidth in the theory of graph minors, branchwidth has more convenient properties in the matroid setting.
• However, instead of using a linear ordering of vertices and a linear sequence of cuts, as in cutwidth, carving width uses cuts derived from a hierarchical clustering of vertices, making it more closely related to treewidth or branchwidth and less similar to the other width parameters involving linear orderings such as pathwidth or bandwidth.
• The branchwidth of a graph is defined similarly to carving width, using hierarchical clusterings, but of the edges of a graph rather than of its vertices; these are called branch-decompositions.

Page preparation took: 286.09 ms.