Edge-Cuts and Rooted Spanning Trees

2022/10/24 by Mohit Daga, Daga, Mohit
Computer Science · Mathematics · #Advanced Graph Theory Research #semigroups and automata theory #Advanced Combinatorial Mathematics

paper · pdf · doi:10.48550/arxiv.2210.13320

Abstract

We give a closed form formula to determine the size of a k-respecting cut. Further, we show that for any k, the size of the k-respecting cut can be found only using the size of 2-respecting cuts.

Related

• The Number of Minimum k-Cuts: Improving the Karger-Stein Bound
• Slim Tree-Cut Width
• Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
• Thin trees for laminar families
• Cutwidth: obstructions and algorithmic aspects