Категория
Информатика
Тип
реферат
Страницы
3 стр.
Дата
27.01.2008
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
20602.zip — 11.87 kb
  • modifikacija-algoritma-opredelenija-klik-grafa-s-parametricheskoj-adaptaciej_20602_1.rtf — 87.36 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

Модификация алгоритма определения клик графа с параметрической адаптацией
В.А. Литвиненко И.Ю. Черненко
1. Основные положения
Кликой графа называется максимальный полный подграф, который не входит ни в один полный подграф более высокого порядка /1/ .
Под точностью решения задачи определения клик графа будем пон
и мать количество выделенных клик. При этом, если выделены все кл и ки графа, то точность решения равна 100%.
Рассматривается класс нериентированных графов без петель и кра
т ных ребер.
Комбинаторная сложность точных алгоритмов определения клик гр
а фа приводит к необходимости использовать приближенные методы при решении задач большой размерности. К таким задачам, в
частности, отн о сятся различные задачи конструкторского проектирования инт е гральных схем, в которых алгоритмы определения клик графа применяются в кач е
стве алгоритмов проектных операций . Известные алгори
т мы /1,2/ позволяют определять только такие семейства клик графа, свойства и мощность которых зависят от структуры решаемых
графов и последов а тельности выполнения самого
алгоритма. От качественного решения алг о ритмов
проектных операций существенно зависит качество решения алг
о ритмов проектных процедур.
Основными факторами, влияющими на качество выполнения алг о
ритмов проектных операций, являются:
требуемая точность решения;
ресурс времени, отведенный на выполнение проектной опер а
ции;
размерность конкретной задачи.
Из указанных факторов известные приближенные методы позволяют учитывать только ограничение на время выполнения алгоритма - р е
сурс времени путем прерывания решения в момент его истечения /2/ .
Однако,



Ваше мнение



CAPTCHA