Vi presenterar en djup-första sökalgoritm för att generera alla maximal klick av en oriktad graf, där beskärningsmetoder används som i Bron-Kerbosch algoritm. Alla maximal cliques som genereras är utdata i en trädliknande form. Därefter visar vi att dess värsta fall tid komplexitet är O(3 n/3 ) för en n-vertex graf. Detta är optimal som en funktion av n, eftersom det finns upp till 3 n/3 maximal klick i en n-vertex graf. Algoritmen visas också att köra mycket snabbt i praktiken genom beräkningsförsök.
Tomita, Tanaka och Takahashi visar att tiden att generera alla maximal klick i n-vertex graf är också O(3 n/3 ) REF.
The worst-case time complexity for generating all maximal cliques and computational experiments
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}