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

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

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



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






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


ПДМ, 2013, номер 3(21), страницы 86–92 (Mi pdm427)  

Прикладная теория графов

О двух задачах аппроксимации взвешенных графов и алгоритмах их решения

А. Р. Ураков, Т. В. Тимеряев

Уфимский государственный авиационный технический университет, г. Уфа, Россия

Аннотация: Рассматриваются две связанные задачи аппроксимации взвешенных графов. В качестве погрешности аппроксимации рассматривается абсолютная величина максимума разностей расстояний между вершинами исходного графа и соответствующими им вершинами графа аппроксимирующего. В первой задаче требуется минимизировать погрешность аппроксимации при заданной размерности аппроксимирующего графа. Во второй – минимизировать размерность аппроксимирующего графа при заданной погрешности. Для задач приводится постановка в терминах задачи разбиения графа, описываются эвристические алгоритмы решения и производится сравнение с решением известным алгоритмом разбиения графа.

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

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

Образец цитирования: А. Р. Ураков, Т. В. Тимеряев, “О двух задачах аппроксимации взвешенных графов и алгоритмах их решения”, ПДМ, 2013, № 3(21), 86–92

Цитирование в формате AMSBIB
\RBibitem{UraTim13}
\by А.~Р.~Ураков, Т.~В.~Тимеряев
\paper О двух задачах аппроксимации взвешенных графов и~алгоритмах их решения
\jour ПДМ
\yr 2013
\issue 3(21)
\pages 86--92
\mathnet{http://mi.mathnet.ru/pdm427}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm427
  • http://mi.mathnet.ru/rus/pdm/y2013/i3/p86

    ОТПРАВИТЬ: 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
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:121
    Полный текст:49
    Литература:27
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019