Computing the Largest Bond and the Maximum Connected Cut of a Graph

Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka +6

The cut-set $\partial (S)$ of a graph $G=(V,E)$ is the set of edges that have one endpoint in $S\subset V$ and the other endpoint in $V\setminus S$, and whenever $G[S]$ is connected…