Graphen ohne induzierten Weg mit vier Knoten, so genannte Cographen, lassen sich als gelabelter Baum kodieren.
Mit dieser Datenstruktur lassen sich viele Optimierungsprobleme, die ansonsten NP-vollständig sind, effizient, meist sogar in Linearzeit lösen.
Dies ändert sich nicht, wenn man wenige P4 zulässt (mit Tinhofer G:
www.fernuni-hagen.deGraphs without induced path on four vertices, so called cographs, can be encoded in a labeled tree.
Using this data structure several optimization problems that are NP-complete in general can be solved efficiently or even in linear time.
This property is invariant if only few P4 are present (with Tinhofer G:
www.fernuni-hagen.deWir konnten durch geeignete Abstraktion neue theoretische Aussagen über die einfachste Form des Problems gewinnen, bei der die Reihenfolge der Karosserietypen unverändert gelassen wird und nur durch die Änderung der Farbreihenfolge die Anzahl der Farbwechsel minimiert werden soll.
Es zeigte sich, dass bereits dieses Problem sowohl für nur zwei verschiedene Karosserietypen und eine beliebige Anzahl von Farben als auch für nur zwei Farben und eine beliebige Anzahl von Karosserietypen NP-vollständig ist.
Für den Fall, dass sowohl die Anzahl der verschiedenen Karosserietypen als auch die Anzahl der Farben beschränkt ist, konnten wir ein dynamisches Programm angeben, mit dem sich das Problem in polynomieller Zeit lösen lässt.
www.zaik.uni-koeln.deUsing suitable abstraction, we obtained new theoretical results on the most simplified problem formulation, in which the sequence of car bodies remains unchanged, and the minimization of color changes is achieved by exclusively changing their color sequence.
Even this problem is NP-complete both in the case of only two car body types and an arbitrary number of colors and in the case of an arbitrary number of car bodies and only two colors.
For the case in which both the number of car bodies and the number of colors are bounded, we developed a dynamic program which solves the problem in polynomial time.
www.zaik.uni-koeln.deMan sucht daher schwächere Eigenschaften, die sich für alle NP-vollständigen Mengen nachweisen lassen.
Beispielsweise kann man zeigen, dass sich jede unendliche NP-vollständige Menge in eine beliebige Anzahl NP-vollständiger Mengen aufteilen lässt.
Damit besitzen alle NP-vollständigen Mengen ein gewisses Maß an Redundanz.
www1.informatik.uni-wuerzburg.deTherefore, researchers are interested in weaker properties that provably hold for all NP-complete sets.
For instance, one can show that all infinite NP-complete sets can be split into an arbitrary number of NP-complete sets.
Hence all these sets share a certain degree of redundancy.
www1.informatik.uni-wuerzburg.de是否要添加一些单词、短语或翻译？
请发送新条目。