Statements (28)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
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 |
theoretical computer science
mathematical optimization |
| gptkbp:complexity |
gptkb:NP-hard
|
| gptkbp:decision |
Is there a cut of size at least k?
|
| gptkbp:definedIn |
graph
|
| gptkbp:field |
combinatorial optimization
theoretical computer science graph theory |
| gptkbp:firstDescribed |
1970s
|
| gptkbp:goal |
partition the vertices into two sets to maximize the number of edges between the sets
|
| https://www.w3.org/2000/01/rdf-schema#label |
Max-Cut
|
| gptkbp:input |
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 |
7
|