| 25.11.2018, 07:25 |
loklodoschko |
Auf diesen Beitrag antworten » |
Instanzen des Cliquen-Problems (CLIQUE)
Meine Frage:
Hallo Leute, ich las mich in die Problematik des Cliquenproblems ein, und musste dabei, aus Mangel an wissenschaftlicheren Quellen, aus dem Internet mein Wissen beziehen. Laut diesem ist das Cliquen-Problem ein Graphentheoretisches Entscheidunsproblem, bei dem es festzustellen gilt, ob in einem Graphen G ein vollständiger Subgraph mit Knotenanzahl n existiert (Eine n-Clique). Meine Frage lautet nun, ob sich verschiedene Instanzen des Problems durch die Größe der Clique, oder die Größe des Graphen unterscheiden. Also: Berechnet man die Laufzeit als f(n) oder als f(G)?
Meine Ideen:
Da die Größe des Subgraphen mit n bezeichnet wird, scheint dies Stark auf ihn zu deuten. Da allerdings n in jedem Fall kleiner gleich |V| sein muss, ist eine Funktion zur Laufzeit der Form x^n auch kleiner gleich x^|V|. Sollten sich nun tatsächlich Instanzen des Problems immer mit dem slebn Graphen beschäftigen, So wäre x^|V| doch ein polynom und selbst ein Ineffizienter Algorithmus hätte dann eine Polynomielle Laufzeit. Jedoch, wie ich zuvor erwähnte, stützt sich mein geringes Wissen in allem Überfluss auf nicht wissenschaftliche Quellen, und so mag alles was ich hier schrieb absoluter Unfug sein. Ich bitte daher innigst um Aufklärung |
