maximaler Schnitt
Sign in to saveAlso known as Max-Cut problem
a cut of a graph whose size is at least the size of any other cut
Wikidata facts
- Instance of
- computational problem
- Subclass of
- cut
- Image
- Max-cut.svg
Show 2 more facts
- computational complexity
- NP-complete
- opposite of
- minimum cut
Sources (2)
via Wikidata · CC0
Article · Deutsch
Der maximale Schnitt eines Graphen ist eine Zerlegung seiner Knotenmenge in zwei Teilmengen, so dass das Gesamtgewicht der zwischen den beiden Teilen verlaufenden Kanten maximal wird. Im Gegensatz zum minimalen Schnitt ist das Problem NP-vollständig.
Abstract from DBpedia / Wikipedia · CC BY-SA