Affordable Access

Równoległe mataheurystyki w kolorowaniu grafów

Authors
Publisher
Національний університет "Львівська політехніка"
Publication Date
Keywords
  • Information Technology
  • Data Analysis And Exploration
  • Nonparametric Estimation
  • Kernel Estimators
  • Control Engineering
  • Decision Support
  • Graph Coloring
  • Graph Coloring Sum
  • Robust Graph Coloring
  • Parallel Metaheuristics
  • Parallel Iterative Algorithms
  • Chromatic Sum
  • Chromatic Sum Number

Abstract

24 Zbigniew Kokosiński Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Cracow University of Technology, Kraków, Poland RÓWNOLEGŁE MATAHEURYSTYKI W KOLOROWANIU GRAFÓW W pracy przedstawiono przegląd zastosowań równoległych metaheurystyk do rozwiązywania problemów kolorowania grafów. Problemy kolorowania grafów (GCP), kolorowania sumacyjnego grafów (GCSP) i kolorowania odpornościowego grafów (RGCP) są NP-zupełne i nie posiadają algorytmów wielomianowych. Z tego powodu dla różnych wariantów podstawowego problemu kolorowania grafów opracowano wiele algorytmów przybliżonych, iteracyjnych i hybrydowych. Ostatnio dla problemu kolorowania grafu i problemów pokrewnych opracowano algorytmy równoległe, w tym równoległe metaheutystyki, takie jak równoległy algorytm wyszukiwania z tabu (PTS), równoległy algorytm genetyczny (PGA) i równoległy algorytm symulowanego wyżarzania (PSA). W weryfikacji eksperymentalnej algorytmów wykorzystano grafy z repozytorium DIMACS oraz grafy losowe. Badania nad zastosowaniem PGA do problemów kolorowania sumacyjnego przyczyniły się do wyznaczenia nowych oszacowań dolnych i górnych sumy chromatycznej i liczby sumy chromatycznej dla klasy benchmarków z bazy DIMACS, znacznie dokładniejszych od znanych oszacowań teoretycznych. Uzyskane wyniki uzasadniają opinię, że równoległe metaheurytyki mogą być efektywnym narzędziem do przybliżonego rozwiązywania zagadnień kolorowania grafów w zastosowaniach praktycznych oraz do eksperymentalnego wyznaczania oszacowań górnych wybranych trudnych obliczeniowo parametrów grafów. Słowa kluczowe: information technology, data analysis and exploration, nonparametric estimation, kernel estimators, control engineering, decision support. In this survey paper applications of parallel metaheuristics in solving graph coloring problems is described. The Graph Coloring Problem (GCP), Graph Coloring Sum Problem (GCSP) and Robust Graph Coloring Pr

There are no comments yet on this publication. Be the first to share your thoughts.