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

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

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



Выч. мет. программирование:
Год:
Том:
Выпуск:
Страница:
Найти






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


Выч. мет. программирование, 2014, том 15, выпуск 2, страницы 304–316 (Mi vmp250)  

Генерация циклов ячеек карты простого планарного графа

Б. Н. Иванов

Дальневосточный федеральный университет

Аннотация: Рассматривается конструктивный метод генерации циклов ячеек (chordless cycles) карты простого планарного графа. Циклы ячеек карты представляются как линейные комбинации циклов {DFS-базиса}. Искомые линейные комбинации строятся явно на основе выделенных свойств структуры вложенности циклов базиса и циклов ячеек карты графа. Карта планарного графа позволила отойти от общепринятого подхода генерации циклов и явно внести геометрию карты в структуру алгоритма. На множестве циклов базиса определяется отношение соседства, которое порождает корневые деревья структуры вложенности циклов. Ячейки карты графа являются результатом обхода данного множества корневых деревьев. Сложность предложенного алгоритма является кубической относительно числа вершин в графе. Рассматривается приложение алгоритма в рамках решения задач на планарном подразбиении.

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

Полный текст: PDF файл (290 kB)
Тип публикации: Статья
УДК: 519.17:519.6
Поступила в редакцию: 05.04.2014

Образец цитирования: Б. Н. Иванов, “Генерация циклов ячеек карты простого планарного графа”, Выч. мет. программирование, 15:2 (2014), 304–316

Цитирование в формате AMSBIB
\RBibitem{Iva14}
\by Б.~Н.~Иванов
\paper Генерация циклов ячеек карты простого планарного графа
\jour Выч. мет. программирование
\yr 2014
\vol 15
\issue 2
\pages 304--316
\mathnet{http://mi.mathnet.ru/vmp250}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vmp250
  • http://mi.mathnet.ru/rus/vmp/v15/i2/p304

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