Przybliżony algorytm wyznaczania kliki maksymalnej grafu

• Autorzy: Schiff K.

Warianty tytułu

EN

Approximate algorithm of graph maximum clique determination

• Języki publikacji: PL

Abstrakty

EN

The new heuristic polynominal graph is presented in this article with time complexity O(n^7) based on new way, in which vertex graph are described.

Słowa kluczowe

PL

izomorfizm grafu; klika maksymalna grafu; macierze sąsiedztwa; wierzchołki odniesienia

EN

graph isomorphism; clicks the maximum graph; neighborhood matrices; reference vertices

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Elektrotechnika
• Rocznik: 2000
• Tom: R. 97, z. 4-E
• Strony: 26--37
• Opis fizyczny: Bibliogr. 8 poz., tab., il.

Twórcy

autor

Schiff K.

Bibliografia

• [1] E. Balas, H. SamueIson, A node covering algorithm, Naval Research Logistics Quart., vol.24, 1977, s.213-33.
• [2] E. Balas, C.S. You, Finding a maximum clique in an graph, SIAM Journal on Comput, vol.15, n.9, 1986, s.1054-67.
• [3] R. Carraghan, P.M. Pardalos, An exact algorithm for the maximum clique problem, Operation Research Letters 9, 1990, s.375-82.
• [4] M. Pelillo, Clique finding relaxation labeling networks, ACCVI95 Second Asian Conference on Computer Vision Procceding, vol2, 1995, s.141-5.
• [5] E.M. Reingold, J. Nievergelt, N. Deo, Algorytmy kombinatoryczne, PWN, Warszawa 1985, s.391.
• [6] K. Schiff, Klika maksymalna grafu, Kwartalnik AGH Elektrotechnika, Kraków 1998, tom 17, zeszyt 4.
• [7] K. Schiff, Efektywność równoległych algorytmów grafowych, praca doktorska, AGH, Kraków 1998.
• [8] K. Schiff, Algorytmy oparte na nowym sposobie opisu wierzchołków „Czasopismo Techniczne" 4E/2000.