Unifying maximum cut and minimum cut of a planar graph
DOI10.1109/12.53581zbMATH Open1395.05173OpenAlexW2129497110MaRDI QIDQ5375441FDOQ5375441
Authors:
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
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (16)
- Simple enumeration of minimal cutsets separating 2 vertices in a class of undirected planar graphs
- 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
- A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
- On tail dependence matrices. The realization problem for parametric families
- The line index and minimum cut of weighted graphs
- Cuts in undirected graphs. I
- Trader multiflow and box-TDI systems in series-parallel graphs
- Maximum cut parameterized by crossing number
- Quantum annealing versus digital computing. An experimental comparison
- Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
- An algorithm for min-cost edge-disjoint cycles and its applications
- From Graph Orientation to the Unweighted Maximum Cut
- Exploiting planarity in separation routines for the symmetric traveling salesman problem
This page was built for publication: Unifying maximum cut and minimum cut of a planar graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5375441)
