Diskussion:Graphpartitionierung

TODO

• Graphiken zur Illustration:
  • Mesh (2d- oder 3d- Netz)
• Beispiel einfügen
• Mathematische Sicht des Partitionierungsproblems
• Spektrale Bisektion: Resultat erklären (Fiedler-Vektor, Laplace-Matrix)

Im Laufe der Zeit hoffe ich diese Aufgaben noch auszuführen. Natürlich ist es niemandem verboten, mir das vorwegzunehmen ;-)

--Chiccodoro 15:18, 27. Jun 2006 (CEST)

========

Beitrag ist ja nicht so gelungen. Es fehlt schon mal die formale Definition von GP. Dananch sollte die Anwendung kommen. (nicht signierter Beitrag von 141.3.24.74 (Diskussion) 20:43, 18. Aug. 2011 (CEST))

Algorithmen

"Die optimale Partition für einen Graphen zu berechnen, ist ein NP-vollständiges Problem."

Selbstkritik: Könnte es sein, dass diese Aussage, die ich dem Werk von Elsner entnommen habe, etwas falsch ist, da laut NP-Vollständigkeit#NP-Äquivalenz der verwendete Begriff nicht für Optimierungsprobleme definiert ist? Stattdessen müsste wohl der Begriff NP-Äquivalenz zutreffen. Allerdings bleibt für mich die Frage offen, wie man in polynomieller Zeit überprüfen soll, ob eine vorgeschlagene Lösung das Optimum ist. --Chiccodoro 08:53, 12. Dez. 2007 (CET)

Link ist tot

Der Link zur TU Chemnitz ist mittlerweile leider tot. (nicht signierter Beitrag von 132.231.35.48 (Diskussion) 19:21, 4. Feb. 2011 (CET))