Gibt es einen effizienten Algorithmus, um den Teilgraphen mit dem größten durchschnittlichen Grad zu finden (welcher der Graph selbst sein kann)?Finden des Untergraphen mit maximalem Durchschnittsgrad. Komplexität?
The paper "Finding a Maximum-Density Subgraph" by Andrew Goldberg gibt einen polynomiellen Algorithmus zur Identifizierung eines solchen Graphen. Es sieht so aus, als ob der Algorithmus logarithmisch viele Aufrufe eines Max-Flow-Algorithmus auf entsprechend konstruierten Graphen durchführt. Nach dem, was ich gelesen habe, sieht es so aus, als sei der Algorithmus nur eine binäre Suche über den durchschnittlichen Grad, bei dem jede Schätzung mit einem maximalen Fluss auf einer Standard-Graph-Konstruktion geprüft wird. Der größte Teil der Komplexität scheint darin zu liegen, zu argumentieren, warum die Konstruktion korrekt ist.
Hoffe, das hilft!