Finding a Maximum Cut of a Planar Graph in Polynomial Time

DOI10.1137/0204019zbMath0321.05120OpenAlexW2073705438MaRDI QIDQ4083698

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

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

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