A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs

DOI10.1155/2017/1267108zbMATH Open1387.90259arXiv1606.05240OpenAlexW2963170238MaRDI QIDQ1748508FDOQ1748508

Authors: Brahim Chaourar 

Publication date: 11 May 2018

Published in: Advances in Operations Research (Search for Journal in Brave)

Abstract: Given a graph $G=(V,E)$, a connected sides cut $$ or $delta(U)$ is the set of edges of E linking all vertices of U to all vertices of $$ such that the induced subgraphs $G[U]$ and $$ 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.

Full work available at URL: https://arxiv.org/abs/1606.05240

Recommendations

• scientific article; zbMATH DE number 4049086
• scientific article; zbMATH DE number 1496855
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• On max cut in cubic graphs
• scientific article; zbMATH DE number 841593

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Reducibility among combinatorial problems
• Graph theory with applications
• Some simplified NP-complete graph problems
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Optimizing cost flows by edge cost and capacity upgrade
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Odd Cuts and Plane Multicommodity Flows
• The real positive semidefinite completion problem for series-parallel graphs
• Scheduling UET-UCT series-parallel graphs on two processors
• The quadratic 0-1 knapsack problem with series-parallel support
• \(k\)-edge connected polyhedra on series-parallel graphs
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• On survivable network polyhedra
• List total colorings of series-parallel graphs
• A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
• A PTAS for weight constrained Steiner trees in series--parallel graphs.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximum cut on line and total graphs
• The traveling salesman problem in graphs with some excluded minors
• An \(O(Kn \log (Kn))\) algorithm for the \(K\)th best spanning tree in series parallel graphs
• Title not available (Why is that?)
• Unifying maximum cut and minimum cut of a planar graph
• A note on the tour problems in two-terminal series-parallel graphs
• The line index and minimum cut of weighted graphs
• The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation
• Minimum Dominating Trail Set for Two-Terminal Series Parallel Graphs

Cited In (10)

• Computing the largest bond and the maximum connected cut of a graph
• Mixed-integer programming techniques for the connected max-\(k\)-cut problem
• A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs
• Title not available (Why is that?)
• SIMPLE MAX-CUT for unit interval graphs and graphs with few \(P4\)s
• Cuts in undirected graphs. I
• A polynomial algorithm for minDSC on a subclass of series Parallel graphs
• A highly efficient algorithm for maximum cut on Halin graphs
• Title not available (Why is that?)
• On the bond polytope

This page was built for publication: A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1748508)