Unifying maximum cut and minimum cut of a planar graph

DOI10.1109/12.53581zbMath1395.05173OpenAlexW2129497110MaRDI QIDQ5375441

No author found.

Publication date: 14 September 2018

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/399213482e8ee060f31ed553e1ce067db42dc4dd

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\) ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Positive planar satisfiability problems under 3-connectivity constraints ⋮ Quantum Annealing versus Digital Computing ⋮ Trader multiflow and box-TDI systems in series-parallel graphs ⋮ On tail dependence matrices. The realization problem for parametric families ⋮ Maximum Cut Parameterized by Crossing Number ⋮ Cuts in undirected graphs. I ⋮ Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs ⋮ Exploiting planarity in separation routines for the symmetric traveling salesman problem ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ An algorithm for min-cost edge-disjoint cycles and its applications ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ The line index and minimum cut of weighted graphs

This page was built for publication: Unifying maximum cut and minimum cut of a planar graph