ГлавнаяАрхивЭволюционно-фрагментарный алгоритм нахождения максимального планарного суграфа

Эволюционно-фрагментарный алгоритм нахождения максимального планарного суграфа | Прикладная дискретная математика. 2015. № 3(29).

Рассматривается задача нахождения максимального планарного суграфа в несе-парабельном неориентированном графе. Показано, что эта задача может быть представлена как задача оптимизации на фрагментарной структуре. Предложен эволюционно-фрагментарный алгоритм поиска приближённых решений задачи.
  • Title Эволюционно-фрагментарный алгоритм нахождения максимального планарного суграфа
  • Headline Эволюционно-фрагментарный алгоритм нахождения максимального планарного суграфа
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(29)
  • Date:
  • DOI
Ключевые слова
граф, максимальный планарный суграф, изометрические циклы, фрагментарная структура, эволюционно-фрагментарный алгоритм, graph, maximally flat part of graph, isometric cycles, fragmented structure, evolutionarily-fragmented algorithm
Авторы
Ссылки
Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. 1104c.
Tamassia R. Handbook of Graph Drawing and Visualization. Boca Raton: Chapman and Hall/CRC, 2013. 844 p.
Курапов С. В., Толок А. В. Методы построения топологического рисунка графа // Автоматика и телемеханика. 2013. №9. C. 78-97.
Курапов С. В., Давидовский М. В. Два подхода к проведению соединений в плоских конструктивах // Компоненты и технологии. 2015. №7. C. 142-147.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416с.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. 512 с.
Харари Ф. Теория графов. М.: Мир, 1973. 300 с.
Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.
Зыков Е. И. Основы теории графов. М.: Наука, 1987. 384 с.
Курапов С. В., Похальчук Т. А. Единичные циклы и разрезы для определения изоморфизма графов // Вюник Запорiзького нацюнального ушверситету: Збiрник наукових праць. Фiз.-мат. науки. 2011. №2. С. 61-68.
Курапов С. В., Савин В. В. Векторная алгебра и рисунок графа. Запорiжжя: ЗДУ, 2003. 200 с.
KavithaT., Liebchen C., MehlhornK., MichailD., et al. Cycle bases in graphs - characterization, algorithms, complexity, and applications // Comput. Sci. Rev. 2009. No.3. P. 199-243.
Козин И. В., Полюга С. И. Фрагментарные модели для некоторых экстремальных задач на графах // Математичш машини i системи. 2014. №1. С. 143-150.
Деза Е. И., Деза М. М. Энциклопедический словарь расстояний. М.: Наука, 2008. 432 с.
Козин И. В., Полюга С. И. О свойствах фрагментарных структур // Вюник Запорiзь-кого нацюнального ушверситету: Збiрник наукових праць. Фiз.-мат. науки. 2012. №1. С.99-106.
ErdSos P. and Rfenyi A. On random graphs I // Publ. Math. Debrecen. 1959. V. 6. P. 290-297.
Эволюционно-фрагментарный алгоритм нахождения максимального планарного суграфа | Прикладная дискретная математика. 2015. № 3(29).
Эволюционно-фрагментарный алгоритм нахождения максимального планарного суграфа | Прикладная дискретная математика. 2015. № 3(29).