Cuts in undirected graphs. I

DOI10.1007/S10559-020-00272-3MaRDI QIDQ2215599zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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

Describes a project that uses

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)