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

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

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



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






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


Дискретный анализ и исследование операций, 2018, том 25, выпуск 2, страницы 19–53
DOI: https://doi.org/10.17377/daio.2018.25.588
(Mi da894)
 

Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

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

С. В. Китаев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\dots$, либо слово вида $yxyx\dots$ (каждое из этих слов может иметь как чётную, так и нечётную длину). Граф $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).
Статья поступила: 11.08.2017
Переработанный вариант: 12.12.2018
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2018, Volume 12, Issue 2, Pages 278–296
DOI: https://doi.org/10.1134/S1990478918020084
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.174
Образец цитирования: С. В. Китаев, А. В. Пяткин, “Графы, представимые в виде слов. Обзор результатов”, Дискретн. анализ и исслед. опер., 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{https://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{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85047875062}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da894
  • https://www.mathnet.ru/rus/da/v25/i2/p19
  • Эта публикация цитируется в следующих 4 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:422
    PDF полного текста:277
    Список литературы:60
    Первая страница:8
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024