Эта публикация цитируется в
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
Аннотация:
В работе обсуждается понятие структурной разреженности, а также отношение этого понятия к введенной авторами для классов графов дихотомии “нигде не плотный / где-то плотный”. Рассматриваются многочисленные проявления этой дихотомии и ее связь с такими понятиями, как устойчивость, независимость, VC-размерность, регулярные разбиения, энтропия, скорость класса, разложение с малой древесной глубиной, квазиширота, покрытие окрестностями, статистика подграфов и др., а также такие аспекты алгоритмической сложности, как разрешимость проверки модели первого порядка при фиксированном параметре.
Библиография: 78 названий.
Ключевые слова:
реляционные структуры, теория графов, нигде не плотный класс, разреженность, VC-размерность, устойчивость, свойство независимости, неглубокий минор, случайно-свободный предел, структурный предел, борелевская структура, моделировка, разложение с малой древесной глубиной, проверка моделей.
УДК:
512.56+
519.71+
519.17
MSC: 03C13,
03C98,
05C99 Поступила в редакцию: 02.06.2015
DOI:
10.4213/rm9688
Полный текст:
PDF файл (1344 kB)
