in perfekten Graphen läßt sich sicher keine Clique in O(n+m) bestimmen. Dafür werden ja gerade Lineare Programme benutzt, soweit ich weiß und deren Laufzeit ist zwar polynomiell, aber nicht linear. gilt der spaß nur für triangulierte graphen, oder gilt er überhaupt? wenn ja, wo steht daß? --Coma 19:35, 24. Feb 2003 (CET)
- Ein O(n+m)-Algorithmus für triangulierte Graphen wird in [1] beschrieben. --FRR 10:40, 24. Jan. 2007 (CET)