Hacker News new | ask | show | jobs
by davidanekstein 518 days 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

1 comments

From wikipedia 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.”
I acknowledge the formal definition, but am wondering how the analogy for treewidth would be tweaked for carving width.