Talk:Branch-decomposition

Definition Ambiguity

This article is very poorly written in that the definitions are very ambiguous and poorly worded. I cannot figure out exactly what the decomposition itself is. From the current article, it appears that the decomposition is a set with two members, one is a set of sets (a ternary tree), while the other is a function (the bijection). However, it is unclear whether this is the intended meaning and if it is, whether the bijection from the "leaves of T to the edge set" is from the edges incident to the leaves of T or whether the intended usage is itself, the vertices that make up the leaves of T. Additionally, according to the definition of an e-separation, the width of an e-separation is only capable of being 1, which would be the vertex that's formed as a result of the contraction along e. I, again, doubt this is the intended usage, but given my limited knowledge of graph theory, I cannot fix either one of these issues. I additionally could not find any reference to branch decompositions in the seminal graph theory text by Diestel. Schmittz (talk) 20:41, 2 July 2010 (UTC)

It didn't help that the link to ternary tree went to completely the wrong place (a different kind of ternary tree not related to the ones used here except for being a tree and having a similar name). I've revised the article to, I hope, make it a little more clear. —David Eppstein (talk) 21:58, 2 July 2010 (UTC)

I appreciate the edits. I did think the branchwidth definition fit better in the definitions section, so I moved it back. Schmittz (talk) 08:52, 6 July 2010 (UTC)

I had an abbreviated version of the definition in the lede so that one could read the lede and get a quick summary of the whole article, as well as a more detailed version of the same definition in the definition section. It doesn't make a lot of sense to me to have both the abbreviated version and the full version in the same place. Also the lede no longer mentions width at all, and the part about graphs of low branchwidth having efficient algorithms is misplaced in the definition section. —David Eppstein (talk) 15:17, 6 July 2010 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Branch-decomposition. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20100924110915/http://www.math.uwaterloo.ca/~jfgeelen/publications/grid.pdf to http://www.math.uwaterloo.ca/~jfgeelen/publications/grid.pdf

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 08:49, 7 November 2016 (UTC)

Update of this article; a more general definition

At the present, there are several topics that are not mentioned in this article. Now I especially think about the wealth of width parameters of graphs that have been defined in terms of a branch decomposition of the vertex set: Rank-width, boolean-width and mim-width are all significant graph parameters, but AFAICS no information can be found of them anywhere on Wikipedia . This article would be a natural place to define them, I think. Furthermore, of the topics that are covered, branchwidth have a prominent seat, while the rest are sort of shoehorned in.

I suggest that the article defines a branch decomposition in terms of a generic set S. Though this is not historically the most common way to depict it, it is more neutral and also more true to the current situation. Then come sections devoted to decompositions over an edge set, a vertex set, the ground set of a matroid, etc. with the relevant graph parameters and other interesting topics. If no-one disagrees with this approach, I am more than happy to start rewriting the article myself.

On a side note: Personally I do not agree with the notion that a branch decomposition is a hierarchical clustering of its ground set. First and foremost because it is not rooted and therefore not hierarchical in nature, but also because there is generally not a measure of closeness between the elements you group together. Comparing it to a hierarchical clustering is fine, though.

Highheath (talk) 18:58, 7 August 2021 (UTC)

Hierarchical clusterings of things other than the edges of graphs are a significant topic, but they are not branch decompositions. It makes more sense to me to put such topics into a separate article, rather than having a "branch decomposition" article that is focused on topics that are not branch decompositions. —David Eppstein (talk) 19:22, 7 August 2021 (UTC)