3 ms·
This sounds a lot like the description of carving width [1], and I was wondering if you could help me understand how the analogy differs between them? [1] http
by davidanekstein 2y ago
This sounds a lot like the description of carving width [1], and I was wondering if you could help me understand how the analogy differs between them?
[1] https://link.springer.com/content/pdf/10.1007/BF01215352.pdf https://link.springer.com/content/pdf/10.1007/BF01215352.pdf
- tnch 2y agoFrom wikipedia https://en.wikipedia.org/wiki/Carving_width#Related_parameters https://en.wikipedia.org/wiki/Carving_width#Related_paramete...: “[…], it can be shown that for any graph, the carving width is greater than or equal to half the branch width, and is less than or equal to the degree times the branchwidth. Because treewidth and branchwidth are always within constant factors of each other, similar bounds can be used to relate carving width to treewidth.”
- davidanekstein 2y agoI acknowledge the formal definition, but am wondering how the analogy for treewidth would be tweaked for carving width.
- deleted 2y ago[deleted]