Method of determining the longest simple chain in a graph with the use of a genetic algorithm

• Autorzy: Mielniczuk Ł. , Strzelecki Ł.

Warianty tytułu

PL

Metoda wyznaczania najdłuższego łańcucha prostego w grafie wykorzystująca algorytm genetyczny

• Języki publikacji: EN

Abstrakty

EN

This paper discusses the issue of determining the longest simple chain in a graph by using a heuristic algorithm - a genetic algorithm. A method enabling the effective determination of the longest chain in any connected, undirected graph without loops.

PL

W artykule rozpatrzono problem wyznaczania najdłuższego łańcucha prostego w grafie wykorzystującą algorytm heurystyczny – algorytm genetyczny. Przedstawiono metodę umożliwiającą efektywne wyznaczanie najdłuższego łańcucha w dowolnym grafie spójnym, nieskierowanym, bez pętli.

Słowa kluczowe

EN

graph theory; Hamiltonian chain; heuristic algorithm; genetic algorithm

PL

teoria grafów; łańcuch Hamiltona; algorytm heurystyczny; algorytm genetyczny

• Wydawca: Instytut Teleinformatyki i Automatyki, Wydział Cybernetyki, Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Przegląd Teleinformatyczny
• Rocznik: 2018
• Tom: T. 6, Nr 3-4 (47)
• Strony: 3--18
• Opis fizyczny: Bibliogr. 4 poz., schem., tab.

Twórcy

autor

Mielniczuk Ł.

• Institute of Teleinformatics and Automation, Faculty of Cybernetics, Military University of Technology ul. Gen. W. Urbanowicza 2, 00-908 Warszawa

autor

Strzelecki Ł.

• Institute of Teleinformatics and Automation, Faculty of Cybernetics, Military University of Technology ul. Gen. W. Urbanowicza 2, 00-908 Warszawa

Bibliografia

• [1] GOLDBERG D., Algorytmy genetyczne i ich zastosowania, Warszawa 2003.
• [2] KORZAN B., Elementy teorii grafów i sieci. Metody i zastosowania, Warszawa 1978.
• [3] JAWORSKI J., Algorytmy teorii grafów. Algorytm Robertsa – Floresa. http://www.staff.amu.edu.pl/~jaworski/agrsyll6.pdf.
• [4] WAŁASZEK J., Reprezentacja grafów w komputerze. http://eduinf.waw.pl/inf/alg/001_search/0124.php.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).