Будь ласка, використовуйте цей ідентифікатор, щоб цитувати або посилатися на цей матеріал: http://ena.lp.edu.ua:8080/handle/ntb/21110
Назва: Parallel metaheuristics in graph coloring
Автори: Kokosiński, Z.
Бібліографічний опис: Kokosiński Z. Parallel metaheuristics in graph coloring / Z. Kokosiński // Вісник Національного університету "Львівська політехніка". – 2012. – № 744 : Комп’ютерні науки та інформаційні технології. – С. 209–214. – Bibliografia: 43 nazwy.
Дата публікації: 2012
Видавництво: Видавництво Львівської політехніки
Теми: graph coloring
graph coloring sum
robust graph coloring
parallel metaheuristics
parallel iterative algorithms
chromatic sum
chromatic sum number
колоризація графів
сумарна колоризація
робастна колоризація
паралельна метаевристика
паралельний ітераційний алгоритм
хроматична сума
число хроматичної суми
Короткий огляд (реферат): In this survey paper applications of parallel metaheuristics to solving graph coloring problems are described. The Graph Coloring Problem (GCP), Graph Coloring Sum Problem (GCSP) and Robust Graph Coloring Problem (RGCP) are known to be NP-complete. They do not have any polynomial algorithms. Therefore, a number of approximation, iterative and hybrid algorithms was developed for their solving. Recently a number of parallel algorithms was proposed for GCP and related coloring problems, including parallel metaheuristics like Parallel Genetic Algorithm (PGA), Parallel Tabu Search (PTS), Parallel Simulated Annealing (PSA) etc. DIMACS benchmarks as well as random graphs were used for their experimental verification. The results obtained for GCSP contributed to finding better lower and upper bounds on chromatic sum and chromatic sum number ьfor many DIMACS graph instances, outperforming results known from the literature. The reported data support a conclusion, that parallel metaheuristics can be used efficiently for approximate solving of many graph coloring problems and for finding better upper bounds of many hard-tocompute graph parameters. Наведено огляд застосувань паралельних метаевристик для вирішення проблем колоризації графів. Проблеми колоризації графів (GCP), сумарної колоризації графів (GCSP) та робастної колоризації графів (RGCP) є NP-повними і не мають поліноміаль- них алгоритмів. З цієї причини для різних варіантів основної проблеми колоризації графів розроблено багато наближених алгоритмів, ітераційних і гібридних. Останнім часом для задачі колоризації графів і подібних їй проблем були розроблені паралельні алгоритми, зокрема паралельні метаевристики, зокрема паралельний алгоритм табу пошуку (PTS), паралельний генетичний алгоритм (PGA) і паралельний алгоритм іміта- ції відпалу (PSA). В експериментальній перевірці алгоритмів використано графи зі сховищем DIMACS, а також випадкові графи. Дослідження застосування PGA для задач сумарної колоризації спричинило визначення нових верхніх і нижніх оцінок хроматичної суми і числа хроматичної суми для класу тестів з бази DIMACS, які є точнішими від відомих теоретичних оцінок. Отримані результати підтверджують думку, що паралельні метаевристики можуть стати потужним інструментом для наближеного розв’язування задач колоризації графів у практичних застосуваннях, а також для експериментального визначення верхньої оцінки обраних параметрів важко обчислювальних графів.
URI (Уніфікований ідентифікатор ресурсу): http://ena.lp.edu.ua:8080/handle/ntb/21110
Тип вмісту : Article
Розташовується у зібраннях:Комп'ютерні науки та інформаційні технології. – 2012. – №744

Файли цього матеріалу:
Файл Опис РозмірФормат 
34-Kokosinski-209-214.pdf166,08 kBAdobe PDFПереглянути/відкрити


Усі матеріали в архіві електронних ресурсів захищені авторським правом, всі права збережені.