Wielomianowy heurystyczny algorytm wyznaczania kliki maksymalnej O(n⁴)

• Autorzy: Schiff K.

Warianty tytułu

EN

Polynominal heuristic algorithm for maximal clique problems

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono wielomianowy heurystyczny algorytm wyznaczania kliki maksymalnej o złożoności obliczeniowej rzędu O(n⁴). Algorytm został oparty o opracowaną metodę sukcesywnego wyznaczania, bezpośrednio z macierzy sąsiedztwa wierzchołków najbardziej nadających się do utworzenia kliki o maksymalnym wymiarze.

EN

In this paper heuristic algorithm with poły nominal computational complexity O(n⁴) for maximal clique problem is presented. This algorithm is based on successive designation of vertex from incidence matrix, which are the most suitable for maximal clique creation.

Słowa kluczowe

PL

klika maksymalna; optymalizacja kombinatoryczna; algorytmy grafowe

EN

maximal clique; combinatorial optimization; graph algorithms

• Wydawca: Wydawnictwa AGH
• Czasopismo: Elektrotechnika i Elektronika
• Rocznik: 2000
• Tom: T. 19, z. 1
• Strony: 17--20
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Schiff K.

• Politechnika Krakowska, Wydział Inżynierii Elektrycznej i Komputerowej, Instytut Automatyki