RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ. Приложение:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ. Приложение, 2014, выпуск 7, страницы 154–157 (Mi pdma136)  

Вычислительные методы в дискретной математике

Структурная декомпозиция графа и её применение для решения оптимизационных задач на разреженных графах

В. В. Быкова

Институт математики и фундаментальной информатики Сибирского федерального университета, г. Красноярск

Аннотация: Формализовано понятие разреженного графа через числовой параметр, известный как древовидная ширина графа. Предложен декомпозиционный подход решения оптимизационных задач на разреженных графах. Этот подход реализует принцип “разделяй и властвуй” и основан на атомарном представлении входного графа. Показано, что атомарное представление графа может быть построено за полиномиальное время. Приведены свойства атомов, определяющие границы применения предлагаемого подхода. Представлены результаты использования атомарного представления графа в решении двух оптимизационных задах: вычисление кратчайших путей и нахождение наибольшей клики графа. Время выполнения результирующих алгоритмов линейно зависит от числа вершин входного графа, что позволяет с их помощью обрабатывать разреженные графы большой размерности за реальное время.

Ключевые слова: разреженный граф, алгоритмы на графах, древовидная ширина, дерево декомпозиции, атом графа.

Полный текст: PDF файл (414 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.178

Образец цитирования: В. В. Быкова, “Структурная декомпозиция графа и её применение для решения оптимизационных задач на разреженных графах”, ПДМ. Приложение, 2014, № 7, 154–157

Цитирование в формате AMSBIB
\RBibitem{Byk14}
\by В.~В.~Быкова
\paper Структурная декомпозиция графа и её применение для решения оптимизационных задач на разреженных графах
\jour ПДМ. Приложение
\yr 2014
\issue 7
\pages 154--157
\mathnet{http://mi.mathnet.ru/pdma136}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdma136
  • http://mi.mathnet.ru/rus/pdma/y2014/i7/p154

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика. Приложение
    Просмотров:
    Эта страница:264
    Полный текст:152
    Литература:29
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020