Biorąc pod uwagę wykres akordowy

Wykres jest akordowy, jeśli nie indukował cykli o długości 4 lub większej. Drzewo klika T z G jest drzewem, w którym wierzchołki drzewa są maksymalne klik z G . Krawędź w T odpowiada minimalnemu separatorowi. Liczba odrębnych drzew kliki może być wykładnicza pod względem liczby wierzchołków na wykresie akordowym.$G$$4$$T$$G$$G$$T$

Zmniejszona klika wykres jest sumą wszystkich drzew klika G . Oznacza to, że ma te same wierzchołki i wszystkie możliwe krawędzie. Jaka jest złożoność obliczania C r ( G ) dla danego G ?$C_r(G)$$G$$C_r(G)$$G$

Myślę, że kiedyś widziałem prezentację, w której twierdzono, że można obliczyć w czasie O ( m + n ) bez dowodu. Oznaczałoby to, że jest tak łatwe, jak obliczanie drzewa kliki G . Czy istnieje odniesienie, które to potwierdza, lub daje wolniejszy algorytm do jego obliczania?$C_r(G)$$O(m+n)$$G$

Złożoność wynosi O (nm) ... z G obliczyć maksymalne kliki i uczynić je wierzchołkami na wykresie H (początkowo bez krawędzi) ... a następnie obliczyć wszystkie minimalne separatory i uporządkować je według rozmiaru ... wybierz największy separator S i wykonaj dowolne dwie kliki C, C 'w sąsiedztwie H (połącz je krawędzią z etykietą S), jeśli C, C' oba zawierają S i znajdują się w różnych połączonych składnikach H (początkowo jest to zawsze prawda, ale może nie będzie później) ... następnie wybierz następny największy separator i zrób to samo ... powtarzaj, aż wszystkie separatory zostaną przetworzone ... wynikowy wykres H jest wykresem zmniejszonej kliki G ... obliczenie maksymalnych klik i minimalnych separatorów zajmuje O (n + m) ... są kliki O (n) i separatory O (n) ... reszta konstrukcji to O (nm), ponieważ przetwarzanie każdego separatora może zająć czas O (m) ... .nie można tego poprawić poniżej O (n ^ 2), chyba że można rozwiązać następujący problem: biorąc pod uwagę wykres G znajdź dwa wierzchołki u, v takie, że N (u) zawiera N (v) ... ten drugi nie jest znany Rozwiązanie O (n + m) ... ... dlatego jest mało prawdopodobne, aby możliwy był algorytm O (n + m) do obliczania grafów z ograniczoną kliką ...

patrz sekcja 5 w M. Habib, J. Stacho: Algorytm czasu wielomianowego dla ulistnienia grafów akordowych, W: Algorytmy - ESA 2009, Nota wykładowa z informatyki 5757/2009, s. 290–300. ( http://www.cs.toronto.edu/~stacho/public/leafage-esa1.pdf )