|
|
Дискретн. анализ и исслед. опер., сер. 1, 2000, том 7, номер 1, страницы 49–66
(Mi da254)
|
 |
|
 |
Эта публикация цитируется в 5 статьях
$E$-свободные двудольные графы
В. В. Лозин
Нижегородский государственный университет им. Н. И. Лобачевского
Аннотация:
Предложена структурная характеризация класса двудольных графов, не содержащих порожденных подграфов, изоморфных графу $E$, где $E$ – граф с вершинами $a$, $b$, $c$, $d$, $e$, $f$ и ребрами $ab$, $bc$, $cd$, $de$, $cf$. Показано, что графы из этого класса распознаются за время $O(n^2)$. Доказана полиномиальная разрешимость в данном классе ряда проблем, являющихся NP-полными на множестве всех двудольных графов. Ил. 3, библиогр. 27.
УДК:
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{http://www.zentralblatt-math.org/zmath/search/?an=Zbl 0949.05073}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da254 http://mi.mathnet.ru/rus/da/v7/s1/i1/p49
 Полный текст:
PDF файл (1966 kB)
Реферативные базы данных:
 
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
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
-
Lozin V.V., “Bipartite graphs without a skew star”, DISCRETE MATHEMATICS, 257:1 (2002), 83–100
 -
Alekseev V.E., Lozin V.V., “Augmenting graphs for independent sets”, DISCRETE APPLIED MATHEMATICS, 145:1 (2004), 3–10
-
Boliac R., Cameron K., Lozin V.V., “On computing the dissociation number and the induced matching number of bipartite graphs”, ARS COMBINATORIA, 72 (2004), 241–253
-
Lozin V., Rautenbach D., “Chordal bipartite graphs of bounded tree- and clique-width”, DISCRETE MATHEMATICS, 283:1–3 (2004), 151–158
|
| Просмотров: |
| Эта страница: | 209 | | Полный текст: | 64 |
|
Пользовательское соглашение