|
gptkbp:instanceOf
|
gptkb:theoretical_computer_science
|
|
gptkbp:application
|
statistical physics
VLSI design
network design
circuit layout
|
|
gptkbp:approximationAlgorithm
|
gptkb:Goemans–Williamson_algorithm
|
|
gptkbp:approximationRatio
|
0.878
|
|
gptkbp:category
|
gptkb:theoretical_computer_science
gptkb:mathematical_optimization
|
|
gptkbp:complexity
|
gptkb:NP-hard
|
|
gptkbp:decision
|
Is there a cut of size at least k?
|
|
gptkbp:definedIn
|
gptkb:graph
|
|
gptkbp:field
|
gptkb:theoretical_computer_science
combinatorial optimization
graph theory
|
|
gptkbp:firstDescribed
|
1970s
|
|
gptkbp:goal
|
partition the vertices into two sets to maximize the number of edges between the sets
|
|
gptkbp:input
|
gptkb:graph
|
|
gptkbp:output
|
partition of vertices
maximum number of crossing edges
|
|
gptkbp:relatedTo
|
minimum cut
graph partitioning
|
|
gptkbp:solvableInPolynomialTime
|
no
|
|
gptkbp:specialCaseSolvableInPolynomialTime
|
planar graphs
graphs with bounded treewidth
|
|
gptkbp:bfsParent
|
gptkb:Maximum_cut_problem
|
|
gptkbp:bfsLayer
|
8
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Max-Cut
|