Cuts in undirected graphs. I

DOI10.1007/S10559-020-00272-3zbMATH Open1472.05043OpenAlexW3045812821MaRDI QIDQ2215599FDOQ2215599

Authors: Yanyan Li 

Publication date: 14 December 2020

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10559-020-00272-3

Recommendations

• Cuts in undirected graphs. II
• Finding the maximum cut by the greedy algorithm
• Combinatorial and geometric properties of the max-cut and min-cut problems
• scientific article; zbMATH DE number 780784
• scientific article; zbMATH DE number 176747

zbMATH Keywords

convex functioncutsspecial polyhedra

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Cites Work

• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Title not available (Why is that?)
• Reducibility among combinatorial problems
• Pseudo-Boolean optimization
• Some simplified NP-complete graph problems
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Weakly bipartite graphs and the max-cut problem
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• The max-cut problem on graphs not contractible to \(K_ 5\)
• A simple min-cut algorithm
• Submodular function minimization
• Title not available (Why is that?)
• A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs
• Unifying maximum cut and minimum cut of a planar graph
• The maximum cut problem
• Finding the maximum cut by the greedy algorithm

Cited In (5)

• Combinatorial and geometric properties of the max-cut and min-cut problems
• Cuts in undirected graphs. II
• Odd Multiway Cut in Directed Acyclic Graphs
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Finding the maximum cut by the greedy algorithm

Uses Software

• Biq Mac

This page was built for publication: Cuts in undirected graphs. I

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