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

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

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


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




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

Успехи математических наук, 2016, том 71, выпуск 1(427), страницы 85–116
DOI: https://doi.org/10.4213/rm9688 (Mi rm9688) 		 
Эта публикация цитируется в 14 научных статьях (всего в 14 статьях)

Структурная разреженность

Я. Нешетрилab, П. Оссона де Мендезac

a Computer Science Institute of Charles University (IUUK), Praha, Czech Republic
b Computer Science Institute of Charles University (ITI), Prague, Czech Republic
c Centre d'Analyse et de Mathèmatiques Sociales (CNRS, UMR 8557), Paris, France
PDF полного текста (1344 kB) PDF английской версии (1055 kB) Список цитирования (14)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/rm9688
Аннотация: В работе обсуждается понятие структурной разреженности, а также отношение этого понятия к введенной авторами для классов графов дихотомии “нигде не плотный / где-то плотный”. Рассматриваются многочисленные проявления этой дихотомии и ее связь с такими понятиями, как устойчивость, независимость, VC-размерность, регулярные разбиения, энтропия, скорость класса, разложение с малой древесной глубиной, квазиширота, покрытие окрестностями, статистика подграфов и др., а также такие аспекты алгоритмической сложности, как разрешимость проверки модели первого порядка при фиксированном параметре.
Библиография: 78 названий.
Ключевые слова: реляционные структуры, теория графов, нигде не плотный класс, разреженность, VC-размерность, устойчивость, свойство независимости, неглубокий минор, случайно-свободный предел, структурный предел, борелевская структура, моделировка, разложение с малой древесной глубиной, проверка моделей.
Финансовая поддержка Номер гранта
European Research Council ERCCZ LL-1201
Agence Nationale de la Recherche ANR-13-BS02-0007
Czech Science Foundation CE-ITI P202/12/G061
Работа первого автора выполнена при поддержке грантов ERCCZ LL-1201 и CE-ITI P202/12/G061, а также Европейской объединенной лаборатории “Structures in Combinatorics” (LEA STRUCO). Работа второго автора выполнена при поддержке гранта ERCCZ LL-1201 и Европейской объединенной лаборатории “Structures in Combinatorics” (LEA STRUCO), а также при частичной поддержке проекта Stint ANR за номером ANR-13-BS02-0007.
Поступила в редакцию: 02.06.2015
Англоязычная версия:
Russian Mathematical Surveys, 2016, Volume 71, Issue 1, Pages 79–107
DOI: https://doi.org/10.1070/RM9688
Реферативные базы данных:
Тип публикации: Статья
УДК: 512.56+519.71+519.17
MSC: 03C13, 03C98, 05C99
Образец цитирования: Я. Нешетрил, П. Оссона де Мендез, “Структурная разреженность”, УМН, 71:1(427) (2016), 85–116; Russian Math. Surveys, 71:1 (2016), 79–107
Цитирование в формате AMSBIB
\RBibitem{NesOss16}
\by Я.~Нешетрил, П.~Оссона де Мендез
\paper Структурная разреженность
\jour УМН
\yr 2016
\vol 71
\issue 1(427)
\pages 85--116
\mathnet{http://mi.mathnet.ru/rm9688}
\crossref{https://doi.org/10.4213/rm9688}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3507464}
\zmath{https://zbmath.org/?q=an:06599755}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2016RuMaS..71...79N}
\elib{https://elibrary.ru/item.asp?id=25707791}
\transl
\jour Russian Math. Surveys
\yr 2016
\vol 71
\issue 1
\pages 79--107
\crossref{https://doi.org/10.1070/RM9688}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000376511100002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84973523453}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/rm9688
  • https://doi.org/10.4213/rm9688
  • https://www.mathnet.ru/rus/rm/v71/i1/p85
    • Эта публикация цитируется в следующих 14 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Успехи математических наук Russian Mathematical Surveys
    Статистика просмотров:
    Страница аннотации:782
    PDF русской версии:157
    PDF английской версии:91
    Список литературы:128
    Первая страница:61
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025