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

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

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



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






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


Дискретн. анализ и исслед. опер., 2018, том 25, номер 2, страницы 19–53 (Mi da894)  

Графы, представимые в виде слов. Обзор результатов

С. В. Китаевa, А. В. Пяткинbc

a University of Strathclyde, Livingstone Tower, 26 Richmond St., Glasgow, G1 1XH, UK
b Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
c Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия

Аннотация: Будем говорить, что буквы $x$ и $y$ чередуются в слове $w$, если при удалении из $w$ всех букв кроме $x$ и $y$ получается либо слово вида $xyxy…$, либо слово вида $yxyx…$ (каждое из этих слов может иметь как чётную, так и нечётную длину). Граф $G=(V,E)$ представим в виде слова, если существует конечное слово $w$ над алфавитом $V$, в котором буквы $x$ и $y$ чередуются тогда и только тогда, когда $xy\in E$.
Графы, представимые в виде слов, включают многие важные классы графов, например: графы пересечения хорд, $3$-графы и графы сравнимости. В настоящей статье даётся полный обзор известных результатов по теории графов, представимых в виде слов, включая самые последние достижения в этой области. Табл. 2, ил. 11, библиогр. 48.

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

Финансовая поддержка Номер гранта
Российская академия наук - Федеральное агентство научных организаций I.5.1, 0314-2016-0014
Работа выполнена при поддержке программы фундаментальных научных исследований СО РАН № I.5.1 (проект 0314-2016-0014).


DOI: https://doi.org/10.17377/daio.2018.25.588

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2018, 12:2, 278–296

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.174
Статья поступила: 11.08.2017
Переработанный вариант: 12.12.2018

Образец цитирования: С. В. Китаев, А. В. Пяткин, “Графы, представимые в виде слов. Обзор результатов”, Дискретн. анализ и исслед. опер., 25:2 (2018), 19–53; J. Appl. Industr. Math., 12:2 (2018), 278–296

Цитирование в формате AMSBIB
\RBibitem{KitPya18}
\by С.~В.~Китаев, А.~В.~Пяткин
\paper Графы, представимые в~виде слов. Обзор результатов
\jour Дискретн. анализ и исслед. опер.
\yr 2018
\vol 25
\issue 2
\pages 19--53
\mathnet{http://mi.mathnet.ru/da894}
\crossref{https://doi.org/10.17377/daio.2018.25.588}
\elib{http://elibrary.ru/item.asp?id=34875789}
\transl
\jour J. Appl. Industr. Math.
\yr 2018
\vol 12
\issue 2
\pages 278--296
\crossref{https://doi.org/10.1134/S1990478918020084}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85047875062}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da894
  • http://mi.mathnet.ru/rus/da/v25/i2/p19

    ОТПРАВИТЬ: 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:108
    Полный текст:5
    Литература:14
    Первая стр.:8

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019