Czytam stary artykuł MC Golumbica na temat wykresów EPT (przecięcie krawędzi ścieżek na drzewie). W artykule pokazano, że liczba maksymalnych klików wystąpienia wykresu EPT jest wielomianowa. Stwierdza, że jeśli wyrocznia zgłasza, że wykres jest wykresem EPT, możliwe jest znalezienie maksymalnej kliki za pomocą standardowego algorytmu wyliczania kliki.
Po pierwsze, jakie są te standardowe algorytmy wyliczania klików? Jeśli istnieje więcej niż jeden, czy możemy powiedzieć, że jeśli liczba maksymalnych klików wykresu jest wielomianowa, to czy możemy zastosować dowolny z tych algorytmów wyliczania? Czy też powinniśmy czerpać specjalny algorytm z algorytmu ogólnego, który wykorzystuje pewne specjalne struktury klasy grafowej?
Z góry dziękuję.
Algorytm Bron-Kerbosch oblicza wszystkie maksymalne kliky na niekierowanym grafie (patrz Wikipeadia ). Najgorszy czas działania to O (3 n / 3 ), najwyraźniej jest on ogólnie bardzo szybki i nadal jest najszybszym znanym algorytmem do obliczania wszystkich maksymalnych klików. Dla nowszych odniesienia zobaczyć papiery V. Stix i Cazals i Karande .
źródło