Abstract
Given a graph G = (V, E), a connected sides cut (U, V\U) or delta (U) is the set of edges of E linking all vertices of U to all vertices of V\U such that the induced subgraphs G[U] and G[V\U] are connected. Given a positive weight function w defined on E, the maximum connected sides cut problem (MAX CS CUT) is to find a connected sides cut Omega such that w(Omega) is maximum. MAX CS CUT is NP-hard. In this paper, we give a linear time algorithm to solve MAX CS CUT for series parallel graphs. We deduce a linear time algorithm for the minimum cut problem in the same class of graphs without computing the maximum flow.