Finding a Maximum Cut of a Planar Graph in Polynomial Time

Cited in

(only showing first 100 items - show all)

Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
A remark on max-cut problem with an application to digital-analogue convertors
Decomposition and optimization over cycles in binary matroids
A polynomial characterization of some graph partitioning problems
Weakly bipartite graphs and the max-cut problem
The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
Compositions in the bipartite subgraph polytope
Facets for the cut cone. I
An algorithm for min-cost edge-disjoint cycles and its applications
Path optimization for graph partitioning problems
Role of redundant constraints for improving dual bounds in polynomial optimization problems
The line index and minimum cut of weighted graphs
Maximum cut on line and total graphs
Node and edge relaxations of the max-cut problem
A graph approximation heuristic for the vertex cover problem on planar graphs
Edge-disjoint odd cycles in planar graphs.
On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
The maximum cardinality cut problem in co-bipartite chain graphs
Finding the maximum cut by the greedy algorithm
A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs
How many circuits determine an oriented matroid?
Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
Master polytopes for cycles of binary matroids
Applications of cut polyhedra. II
On a positive semidefinite relaxation of the cut polytope
New algorithms for the weighted maximum cut problem on graphs
A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
On the maximum cardinality cut problem in proper interval graphs and related graph classes
Notes on graph product structure theory
Cuts in undirected graphs. I
Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
Hypergraph cuts above the average
On planar valued CSPs
Parameterized algorithms for min-max multiway cut and list digraph homomorphism
Obtaining a planar graph by vertex deletion
Planar graph bipartization in linear time
Triangle-free subcubic graphs with minimum bipartite density
Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
Finding a maximum minimal separator: graph classes and fixed-parameter tractability
Computing the largest bond and the maximum connected cut of a graph
SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
Vertex-coloring with star-defects
Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
Max-Cut and containment relations in graphs
Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
Linear-time approximation for maximum weight matching
A polynomial algorithm for the max-cut problem on graphs without long odd cycles
A nonmonotone GRASP
Minimum Linear Arrangement of Series-Parallel Graphs
Approximation Algorithms for Geometric Intersection Graphs
Obtaining a Planar Graph by Vertex Deletion
Increasing the minimum degree of a graph by contractions
Partitioning planar graphs: a fast combinatorial approach for max-cut
\textsc{max-cut} and containment relations in graphs
Online maximum directed cut
The \(st\)-bond polytope on series-parallel graphs
On the cut polytope
Approximating unique games using low diameter graph decomposition
Hitting weighted even cycles in planar graphs
Complexity and polynomially solvable special cases of QUBO
Fast Distributed Approximation for Max-Cut
A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
Quantum annealing versus digital computing. An experimental comparison
Maximum cut parameterized by crossing number
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
scientific article; zbMATH DE number 4193718 (Why is no real title available?)
Packing and covering odd cycles in cubic plane graphs with small faces
Packing and covering odd cycles in cubic plane graphs with small faces
The max-cut problem on graphs not contractible to \(K_ 5\)
The complexity of bottleneck labeled graph problems
Synchronized Planarity with Applications to Constrained Planarity Problems
Disjoint total dominating sets in near‐triangulations
Complexity of maximum cut on interval graphs
Finding dense subgraphs
Maximum bipartite subgraphs of geometric intersection graphs
An experimental evaluation of semidefinite programming and spectral algorithms for max cut
Cutting Barnette graphs perfectly is hard
Canonical cuts of path powers
Euclidean maximum matchings in the plane -- local to global
The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
O(1) Steiner point removal in series-parallel graphs
Packing cycles in planar and bounded-genus graphs
Augmenting plane straight-line graphs to meet parity constraints
On 1-skeleton of the cut polytopes
Complexity framework for forbidden subgraphs. I: The framework
Pliability and approximating Max-CSPs
Complexity of maximum cut on interval graphs
Colorful vertex recoloring of bipartite graphs
Approximating maximum cut on interval graphs and split graphs beyond Goemans-Williamson
Triangles improve 0.878 approximation for Maxcut
Edge-contraction problems
On some weakly bipartite 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
Approximate min-max relations for odd cycles in planar graphs
MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
Dynamics of neural networks over undirected graphs
Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel

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

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