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

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

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



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






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


Дискретн. анализ и исслед. опер., сер. 1, 2000, том 7, номер 1, страницы 49–66 (Mi da254)  

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

$E$-свободные двудольные графы

В. В. Лозин

Нижегородский государственный университет им. Н. И. Лобачевского

Аннотация: Предложена структурная характеризация класса двудольных графов, не содержащих порожденных подграфов, изоморфных графу $E$, где $E$ – граф с вершинами $a$, $b$, $c$, $d$, $e$, $f$ и ребрами $ab$, $bc$, $cd$, $de$, $cf$. Показано, что графы из этого класса распознаются за время $O(n^2)$. Доказана полиномиальная разрешимость в данном классе ряда проблем, являющихся NP-полными на множестве всех двудольных графов. Ил. 3, библиогр. 27.

Полный текст: PDF файл (1966 kB)

Реферативные базы данных:
УДК: 519.17
Статья поступила: 07.09.1999

Образец цитирования: В. В. Лозин, “$E$-свободные двудольные графы”, Дискретн. анализ и исслед. опер., сер. 1, 7:1 (2000), 49–66

Цитирование в формате AMSBIB
\RBibitem{Loz00}
\by В.~В.~Лозин
\paper $E$-свободные двудольные графы
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2000
\vol 7
\issue 1
\pages 49--66
\mathnet{http://mi.mathnet.ru/da254}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1767870}
\zmath{https://zbmath.org/?q=an:0949.05073}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da254
  • http://mi.mathnet.ru/rus/da/v7/s1/i1/p49

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Boliac R., Lozin V., “On the clique-width of graphs in hereditary classes”, Algorithms and Computation, Proceedings, Lecture Notes in Computer Science, 2518, 2002, 44–54  crossref  mathscinet  zmath  isi  scopus
    2. Lozin V.V., “Bipartite graphs without a skew star”, Discrete Math, 257:1 (2002), 83–100  crossref  mathscinet  zmath  isi  scopus
    3. Alekseev V.E., Lozin V.V., “Augmenting graphs for independent sets”, Discrete Appl Math, 145:1 (2004), 3–10  crossref  mathscinet  zmath  isi  scopus
    4. Boliac R., Cameron K., Lozin V.V., “On computing the dissociation number and the induced matching number of bipartite graphs”, Ars Combin, 72 (2004), 241–253  mathscinet  zmath  isi
    5. Lozin V., Rautenbach D., “Chordal bipartite graphs of bounded tree- and clique-width”, Discrete Math, 283:1–3 (2004), 151–158  crossref  mathscinet  zmath  isi  scopus
    6. Bonomo F., Duran G., Safe M.D., Wagler A.K., “On Minimal Forbidden Subgraph Characterizations of Balanced Graphs”, Discrete Appl. Math., 161:13-14 (2013), 1925–1942  crossref  mathscinet  zmath  isi  scopus
    7. О. И. Дугинов, “Сложность задач покрытия графа наименьшим числом полных двудольных графов”, Тр. Ин-та матем., 22:1 (2014), 51–69  mathnet
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:345
    Полный текст:130
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019