Finding a Maximum Cut of a Planar Graph in Polynomial Time

DOI10.1137/0204019zbMath0321.05120OpenAlexW2073705438MaRDI QIDQ4083698

Frank Owen Hadlock

Publication date: 1975

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0204019

Mathematics Subject Classification ID

Related Items (90)

A graph approximation heuristic for the vertex cover problem on planar graphs ⋮ Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\) ⋮ Euclidean maximum matchings in the plane -- local to global ⋮ Decomposition and optimization over cycles in binary matroids ⋮ Hitting Weighted Even Cycles in Planar Graphs ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Applications of cut polyhedra. II ⋮ Unnamed Item ⋮ Minimum Linear Arrangement of Series-Parallel Graphs ⋮ Fast Distributed Approximation for Max-Cut ⋮ On a positive semidefinite relaxation of the cut polytope ⋮ Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ A nonmonotone GRASP ⋮ A polynomial characterization of some graph partitioning problems ⋮ New algorithms for the weighted maximum cut problem on graphs ⋮ On planar valued CSPs ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ The max-cut problem on graphs not contractible to \(K_ 5\) ⋮ Unnamed Item ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Approximate min-max relations for odd cycles in planar graphs ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ Increasing the minimum degree of a graph by contractions ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs ⋮ Dynamics of neural networks over undirected graphs ⋮ Quantum Annealing versus Digital Computing ⋮ Synchronized Planarity with Applications to Constrained Planarity Problems ⋮ Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel ⋮ Approximation Algorithms for Geometric Intersection Graphs ⋮ Obtaining a Planar Graph by Vertex Deletion ⋮ Disjoint total dominating sets in near‐triangulations ⋮ Complexity of maximum cut on interval graphs ⋮ The maximum cardinality cut problem in co-bipartite chain graphs ⋮ Obtaining a planar graph by vertex deletion ⋮ Partitioning planar graphs: a fast combinatorial approach for max-cut ⋮ Maximum Cut Parameterized by Crossing Number ⋮ \textsc{max-cut} and containment relations in graphs ⋮ The st-bond polytope on series-parallel graphs ⋮ Finding the maximum cut by the greedy algorithm ⋮ Online maximum directed cut ⋮ Cuts in undirected graphs. I ⋮ Edge-disjoint odd cycles in planar graphs. ⋮ Weakly bipartite graphs and the max-cut problem ⋮ Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs ⋮ The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ On routing in VLSI design and communication networks ⋮ A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ A polynomial algorithm for the max-cut problem on graphs without long odd cycles ⋮ The performance of an eigenvalue bound on the max-cut problem in some classes of graphs ⋮ Compositions in the bipartite subgraph polytope ⋮ Facets for the cut cone. I ⋮ A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs ⋮ An algorithm for min-cost edge-disjoint cycles and its applications ⋮ Planar graph bipartization in linear time ⋮ Maximum cut in fuzzy nature: models and algorithms ⋮ Triangle-free subcubic graphs with minimum bipartite density ⋮ Optimal cuts in graphs and statistical mechanics ⋮ Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem ⋮ Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm ⋮ Packing and covering odd cycles in cubic plane graphs with small faces ⋮ max-cut and Containment Relations in Graphs ⋮ How many circuits determine an oriented matroid? ⋮ Packing and covering odd cycles in cubic plane graphs with small faces ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ The complexity of bottleneck labeled graph problems ⋮ Vertex-Coloring with Star-Defects ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ Maximum cuts in edge-colored graphs ⋮ Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ On the maximum cardinality cut problem in proper interval graphs and related graph classes ⋮ Notes on graph product structure theory ⋮ A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs ⋮ Path optimization for graph partitioning problems ⋮ On the cut polytope ⋮ Master polytopes for cycles of binary matroids ⋮ Role of redundant constraints for improving dual bounds in polynomial optimization problems ⋮ Hypergraph cuts above the average ⋮ The line index and minimum cut of weighted graphs ⋮ Edge-contraction problems ⋮ Maximum cut on line and total graphs ⋮ On some weakly bipartite graphs ⋮ Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions ⋮ Node and edge relaxations of the max-cut problem ⋮ Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs ⋮ A remark on max-cut problem with an application to digital-analogue convertors

This page was built for publication: Finding a Maximum Cut of a Planar Graph in Polynomial Time