Live briefing
Everything about Maximum cut
Problem in graph theory
In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Maximum cutA 5-minute orientation
- Skim a recent paper: Arbitrarily High-Order Maximum Bound Preserving Schemes with Cut-off Postprocessing for Allen–Cahn EquationsInfluential work since 2022
- Pick up a classic book: Data structures and algorithm analysis in CThe most-reprinted book on the subject
- Read the landmark paper: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingCited 2,528 times
- Go sideways: Feedback arc setA closely related topic
- Go sideways: PlanarizationA closely related topic
📖 Definitions
Noun A cut whose size is at least the size of any other cut; a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Finding a Maximum Cut of a Planar Graph in Polynomial Time
Laplacian eigenvalues and the maximum cut problem
Improving benders decomposition using maximum feasible subsystem (MFS) cut generation strategy
Multiobjective hypergraph-partitioning algorithms for cut and maximum subdomain-degree minimization
Inverse maximum flow and minimum cut problems
A Branch and Cut solver for the maximum stable set problem
Unifying maximum cut and minimum cut of a planar graph
🆕 Influential since 2022
Arbitrarily High-Order Maximum Bound Preserving Schemes with Cut-off Postprocessing for Allen–Cahn Equations
Anthropic cut marks in extinct megafauna bones from the Pampean region (Argentina) at the last glacial maximum
Benchmarking quantum optimization for the maximum-cut problem on a superconducting quantum computer
Lower Bounds for Maximum Weighted Cut
Solving the maximum cut problem using Harris Hawk Optimization algorithm
📚 Books worth reading
Data structures and algorithm analysis in CMark Allen Weiss · 1993
Discrete mathematicsNorman Biggs · 1985- 📕Human rights and public financeAoife Nolan, Rory O'Connell · 2013
The Big BreachRichard Tomlinson · 2001
Algorithm designMichael T. Goodrich, Roberto Tamassia · 2001
Linguistic structure predictionNoah A. Smith · 2011
The traveling salesman problem and its variationsGregory Gutin · 2002- 📕Maximum cutting yields for 6/4 ponderosa pine shop lumberKent A McDonald · 1983
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Feedback arc set In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at…
- Planarization In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar…
- Clique cover In graph theory, a clique cover or partition into cliques of a given undirected graph is a collection of cliques that cover the whole graph. Generally…
- Independent set (graph theory) In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a…
- Clique problem In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete…
- Set splitting problem In computational complexity theory, the set splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide…
- Cut (graph theory) In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one…
- Connected dominating set In graph theory, a connected dominating set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph. A connected…