|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Остовное дерево с большим числом висячих вершин
Д. В. Карпов
Аннотация:
Для связного графа $G(V,E)$, в котором никакие две вершины степени 2 не смежны, доказывается существование остовного дерева, в котором более чем $|V|/5$ вершин являются висячими. Доказательства содержат описание полиномиального алгоритма построения такого остовного дерева. Доказывается, что константу 1/5 в этой оценке нельзя заменить на большую.
Статья поступила: 25.05.2000 Переработанный вариант поступил: 05.02.2001
Образец цитирования:
Д. В. Карпов, “Остовное дерево с большим числом висячих вершин”, Дискрет. матем., 13:1 (2001), 63–72; Discrete Math. Appl., 11:2 (2002), 163–171
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm273https://doi.org/10.4213/dm273 https://www.mathnet.ru/rus/dm/v13/i1/p63
|
Статистика просмотров: |
Страница аннотации: | 589 | PDF полного текста: | 372 | Список литературы: | 72 | Первая страница: | 1 |
|