Proc. Estonian Acad. Sci. Engin., 1995, 1, 2, 113-138

EXTRACTING OF ALL MAXIMAL CLIQUES: (pdf)
MONOTONE SYSTEM APPROACH

Rein KUUSIK

Tallinna Tehnikaülikooli Informaatikainstituut (Department of Informatics, Tallinn Technical University), Raja 15, EE-0026 Tallinn, Eesti (Estonia), e-mail: mailto: kuusik@cc.ttu.ee

Presented by L. Mõtus
Received 8 November 1995, accepted 31 January 1996

Abstract.

NP-complicated problems have been described in the graph theory. An example is the extracting of all maximal cliques from a graph. However, complexity is linear to the number of maximal cliques. This paper discusses a new approach for extracting maximal cliques, based on the monotone system theory. The complexity of the presented algorithms is linear to the number of maximal cliques.

Key words: theory of monotone system, graph, clique

KÕIKIDE MAKSIMAALSETE KLIKKIDE ERALDAMINE:
MONOTOONSETE SÜSTEEMIDE TEORIA KÄSITLUS

Rein KUUSIK

Artiklis on käsitletud orienteerimata lõplikest graafidest kõikide maksimaalsete klikkide eraldamist monotoonsete süsteemide teooria seisukohast. See problem on NP- keeruline, maailma parimate algoritmide keerukus on lineaarne graafi maksimaalsete klikkide arvusse. On esitatud ja tõestatud monotoonsete süsteemide teoorial baseeruvad algoritmid, nn. MONS-algoritmid, vaadeldava probleemi lahendamiseks. Nende puhul on lähtitud graafi seosmaatiksist, millele on ehitatud monotoonne süsteem. Kirjeldatud lähenemine võimaldas luua terve rea efetiivseid algoritme, mille keerukus on lineaarne graafi maksimaalsete klikkide suhtes. Kirjeldatud teooria ja meetod on graafist suurima kliki eraldaminse efektiivsete algoritmide loomise alus.