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

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

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


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




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

Дискретный анализ и исследование операций, 2008, том 15, выпуск 6, страницы 3–10 (Mi da552)  
Эта публикация цитируется в 9 научных статьях (всего в 9 статьях)

Критерий граничности и его применения

В. Е. Алексеев, Д. С. Малышев

Нижегородский государственный университет им. Н. И. Лобачевского
PDF полного текста (241 kB) Список цитирования (9)
Список литературы:
PDF
HTML
Аннотация: Даётся новое определение граничного класса графов и доказывается критерий граничности. В качестве примера его применения рассматривается класс, состоящий из графов, у которых каждая компонента связности является деревом с не более чем тремя листьями. Известен ряд задач, для которых этот класс является граничным. Получены достаточные условия его граничности и доказано, что он является граничным для задач о наибольшем двудольном подграфе и наибольшем планарном подграфе. Библиогр. 8.
Ключевые слова: вычислительная сложность, граничный класс, задача о наибольшем подграфе.
Статья поступила: 16.06.2008
Переработанный вариант: 01.10.2008
Реферативные базы данных:
УДК: 519.178
Образец цитирования: В. Е. Алексеев, Д. С. Малышев, “Критерий граничности и его применения”, Дискретн. анализ и исслед. опер., 15:6 (2008), 3–10
Цитирование в формате AMSBIB
\RBibitem{AleMal08}
\by В.~Е.~Алексеев, Д.~С.~Малышев
\paper Критерий граничности и~его применения
\jour Дискретн. анализ и исслед. опер.
\yr 2008
\vol 15
\issue 6
\pages 3--10
\mathnet{http://mi.mathnet.ru/da552}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2543142}
\zmath{https://zbmath.org/?q=an:1249.05363}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da552
  • https://www.mathnet.ru/rus/da/v15/i6/p3
    • Эта публикация цитируется в следующих 9 статьяx:
    1. Lozin V.V., Malyshev D.S., “Vertex Coloring of Graphs With Few Obstructions”, Discrete Appl. Math., 216:1, SI (2017), 273–280  crossref  mathscinet  zmath  isi  scopus
    2. D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Сиб. электрон. матем. изв., 11 (2014), 811–822  mathnet
    3. Д. С. Малышев, “Анализ сложности задачи о рёберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами”, Дискретн. анализ и исслед. опер., 19:1 (2012), 74–96  mathnet  mathscinet
    4. Д. С. Малышев, “О пересечении и симметрической разности семейств граничных классов для задач о раскраске и о хроматическом числе”, Дискрет. матем., 24:2 (2012), 75–78  mathnet  crossref  mathscinet  elib; D. S. Malyshev, “On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number”, Discrete Math. Appl., 21:5-6 (2011), 645–649  crossref
    5. Д. С. Малышев, В. Е. Алексеев, “Граничные классы для задач о списковом ранжировании относительно лесов”, Дискретн. анализ и исслед. опер., 18:6 (2011), 61–70  mathnet  mathscinet  zmath
    6. Д. С. Малышев, “О бесконечности множества граничных классов в задаче о рёберной 3-раскраске”, Дискретн. анализ и исслед. опер., 16:1 (2009), 37–43  mathnet  mathscinet  zmath; D. S. Malyshev, “On infinity of the set of boundary classes for the 3-edge-colorability problem”, J. Appl. Industr. Math., 4:2 (2010), 213–217  crossref
    7. Д. С. Малышев, “Граничные классы графов для некоторых задач распознавания”, Дискретн. анализ и исслед. опер., 16:2 (2009), 85–94  mathnet  mathscinet  zmath
    8. Д. С. Малышев, “Континуальные множества граничных классов графов для задач о раскраске”, Дискретн. анализ и исслед. опер., 16:5 (2009), 41–51  mathnet  mathscinet  zmath
    9. Д. С. Малышев, “О минимальных сложных классах графов”, Дискретн. анализ и исслед. опер., 16:6 (2009), 43–51  mathnet  mathscinet  zmath
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:580
    PDF полного текста:118
    Список литературы:72
    Первая страница:12
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025