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

DOI10.1155/2017/1267108zbMath1387.90259arXiv1606.05240OpenAlexW2963170238MaRDI QIDQ1748508

Brahim Chaourar

Publication date: 11 May 2018

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

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)

Related Items (4)

Computing the largest bond and the maximum connected cut of a graph ⋮ On the bond polytope ⋮ Cuts in undirected graphs. I ⋮ Mixed-integer programming techniques for the connected max-\(k\)-cut problem

Cites Work

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

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