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.