A linear time algorithm for a variant of the max cut problem in series parallel graphs

Brahim Chaourar

Given a graph $G=(V,E)$, a connected sides cut $(U,V\backslash U)$ or $\delta (U)$ is the set of edges of E linking all vertices of U to all vertices of $V\backslash U$ such that the i…