abstract:

Given a graph G=(V, E), a connected 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 connected maximum ccut problem (CMC) is to find a connected cut \Omega such that w(\Omega) is maximum among all connected cuts. CMC is NP-hard even for planar graphs. In this paper, we give a linear time algorithm to solve CMC in 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.

2010 Mathematics Subject Classification: 90C27, 90C57.

Key words and phrases: maximum cut; connected maximum cut, linear time algorithm, series parallel graphs, 2-sums of graphs, minimum cut.