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

DOI10.1155/2017/1267108MaRDI QIDQ1748508zbMATH OpenOpenAlexFDO

Authors Brahim Chaourar

Publication date 11 May 2018

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

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(10)

• On the bond polytope
• 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
• scientific article; zbMATH DE number 4049086 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 841593 (Why is no real title available?)

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)