Finding the maximum cut by the greedy algorithm

DOI10.1007/s10559-018-0075-3zbMath1403.05151OpenAlexW2892794341MaRDI QIDQ1711379

F. A. Sharifov

Publication date: 17 January 2019

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

Full work available at URL: https://doi.org/10.1007/s10559-018-0075-3

zbMATH Keywords

maximum cutlinear orderingbipartite subgraph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Cuts in undirected graphs. I ⋮ Cuts in undirected graphs. II

Cites Work

• Unnamed Item
• Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem
• Submodular functions and optimization.
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

This page was built for publication: Finding the maximum cut by the greedy algorithm