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

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

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


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




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

Дискретный анализ и исследование операций, 2009, том 16, выпуск 6, страницы 43–51 (Mi da593)  
Эта публикация цитируется в 11 научных статьях (всего в 11 статьях)

О минимальных сложных классах графов

Д. С. Малышев

Нижегородский государственный университет, г. Н. Новгород, Россия
PDF полного текста (231 kB) Список цитирования (11)
Список литературы:
PDF
HTML
Аннотация: Рассматриваются понятия минимального сложного и граничного классов графов. Доказывается, что для задачи распознавания принадлежности наследственному классу графов не существует минимальных сложных классов. Указываются граничные и минимальные сложные классы графов для задач о списковом ранжировании. Эти классы графов являются первыми примерами минимальных сложных классов, а также первыми примерами сложных граничных классов. Библиогр. 9.
Ключевые слова: вычислительная сложность, минимальный сложный класс, граничный класс, распознавание наследственного свойства, задачи о списковом ранжировании.
Статья поступила: 10.04.2009
Переработанный вариант: 20.07.2009
Реферативные базы данных:
УДК: 519.178
Образец цитирования: Д. С. Малышев, “О минимальных сложных классах графов”, Дискретн. анализ и исслед. опер., 16:6 (2009), 43–51
Цитирование в формате AMSBIB
\RBibitem{Mal09}
\by Д.~С.~Малышев
\paper О минимальных сложных классах графов
\jour Дискретн. анализ и исслед. опер.
\yr 2009
\vol 16
\issue 6
\pages 43--51
\mathnet{http://mi.mathnet.ru/da593}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2649141}
\zmath{https://zbmath.org/?q=an:1249.05368}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da593
  • https://www.mathnet.ru/rus/da/v16/i6/p43
    • Эта публикация цитируется в следующих 11 статьяx:
    1. Д. С. Малышев, “Критические элементы в комбинаторно замкнутых семействах классов графов”, Дискретн. анализ и исслед. опер., 24:1 (2017), 81–96  mathnet  crossref  mathscinet  elib; D. S. Malyshev, “Critical elements in combinatorially closed families of graph classes”, J. Appl. Industr. Math., 11:1 (2017), 99–106  crossref
    2. Д. С. Малышев, “Критические классы графов для задачи о рёберном списковом ранжировании”, Дискретн. анализ и исслед. опер., 20:6 (2013), 59–76  mathnet  mathscinet; D. S. Malyshev, “Critical graph classes for the edge list-ranking problem”, J. Appl. Industr. Math., 8:2 (2014), 245–255  crossref
    3. Д. С. Малышев, “Анализ сложности задачи о рёберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами”, Дискретн. анализ и исслед. опер., 19:1 (2012), 74–96  mathnet  mathscinet
    4. Малышев Д.С., “О связи понятий граничного и минимального сложного классов графов”, Вестник Нижегородского университета им. Н.И. Лобачевского, 2012, № 2-1, 149–151  elib
    5. Д. С. Малышев, “Экстремальные множества графов при решении задачи демаркации в семействе наследственно замкнутых классов графов”, Дискрет. матем., 24:4 (2012), 91–103  mathnet  crossref  mathscinet  elib; D. S. Malyshev, “Extremal sets of graphs in the problem of demarcation in the family of hereditary closed classes of graphs”, Discrete Math. Appl., 22:5-6 (2012), 595–608  crossref
    6. Алексеев В.Е., Захарова Д.В., Малышев Д.С., Мокеев Д.Б., Сорочан С.В., “Некоторые результаты о наследственных классах графов. ii”, Вестник нижегородского университета им. Н.И. Лобачевского, 2012, 115–120 Some results on hereditary classes of graphs. ii  elib
    7. Д. С. Малышев, “Минимальные сложные классы графов для задачи о рёберном списковом ранжировании”, Дискретн. анализ и исслед. опер., 18:1 (2011), 70–76  mathnet  mathscinet  zmath
    8. Д. С. Малышев, В. Е. Алексеев, “Граничные классы для задач о списковом ранжировании относительно лесов”, Дискретн. анализ и исслед. опер., 18:6 (2011), 61–70  mathnet  mathscinet  zmath
    9. Korpelainen N., Lozin V.V., Malyshev D.S., Tiskin A., “Boundary properties of graphs for algorithmic graph problems”, Theoret Comput Sci, 412:29 (2011), 3545–3554  crossref  mathscinet  zmath  isi  elib  scopus
    10. Алексеев В.Е., Замараев В.А., Захарова Д.В., Малышев Д.С., Мокеев Д.Б., “Некоторые результаты о наследственных классах графов”, Вестник Нижегородского университета им. Н.И. Лобачевского, 2011, № 6-1, 169–173  elib
    11. Малышев Д.С., “Последовательные минимумы решетки наследственных классов графов для задачи о реберном списковом ранжировании”, Вестн. Нижегородского ун-та им. Н.И. Лобачевского, 2010, № 4, 133–136  elib
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:531
    PDF полного текста:113
    Список литературы:56
    Первая страница:7
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025