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

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

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



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






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


ПДМ. Приложение, 2015, выпуск 8, страницы 142–144 (Mi pdma205)  

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

Вычисление верхней оценки вершинной целостности графа на основе минимальных сепараторов

В. В. Быкова, Ю. И. Кириллов

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

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

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

DOI: https://doi.org/10.17223/2226308X/8/55

Полный текст: PDF файл (526 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.178

Образец цитирования: В. В. Быкова, Ю. И. Кириллов, “Вычисление верхней оценки вершинной целостности графа на основе минимальных сепараторов”, ПДМ. Приложение, 2015, № 8, 142–144

Цитирование в формате AMSBIB
\RBibitem{BykKir15}
\by В.~В.~Быкова, Ю.~И.~Кириллов
\paper Вычисление верхней оценки вершинной целостности графа на основе минимальных сепараторов
\jour ПДМ. Приложение
\yr 2015
\issue 8
\pages 142--144
\mathnet{http://mi.mathnet.ru/pdma205}
\crossref{https://doi.org/10.17223/2226308X/8/55}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdma205
  • http://mi.mathnet.ru/rus/pdma/y2015/i8/p142

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