A Linear Time Algorithm for a Variant of the MAX CUT Problem in Series Parallel Graphs

Brahim Chaourar

Advances in Operations Research, 2017, vol. 2017, 1-4

Abstract:

Given a graph , a connected sides cut or is the set of edges of linking all vertices of to all vertices of such that the induced subgraphs and are connected. Given a positive weight function defined on , the maximum connected sides cut problem (MAX CS CUT) is to find a connected sides cut such that 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.

Date: 2017
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/AOR/2017/1267108.pdf (application/pdf)
http://downloads.hindawi.com/journals/AOR/2017/1267108.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlaor:1267108

DOI: 10.1155/2017/1267108

Access Statistics for this article

More articles in Advances in Operations Research from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().