|
Проблемы передачи информации, 2017, том 53, выпуск 4, страницы 3–15
(Mi ppi2249)
|
|
|
|
Эта публикация цитируется в 9 научных статьях (всего в 9 статьях)
Теория кодирования
Числа независимости случайных подграфов некоторого дистанционного графа
Н. М. Деревянко, С. Г. Киселев Московский физико-технический институт (государственный университет)
Аннотация:
Дистанционным графом $G(n,2,1)$ называется граф, вершины которого отождествляются с двухэлементными подмножествами множества $\{1,2,\dots,n\}$, а ребро между вершинами проведено в том случае, если соответствующие подмножества имеют ровно один общий элемент. Случайный подграф $G_p(n,2,1)$ в модели Эрдеша–Реньи получается включением каждого ребра графа $G(n,2,1)$ с вероятностью $p$ независимо от остальных ребер. Найдена нижняя оценка числа независимости случайного подграфа $G_{1/2}(n,2,1)$.
Поступила в редакцию: 25.02.2017 После переработки: 04.05.2017
Образец цитирования:
Н. М. Деревянко, С. Г. Киселев, “Числа независимости случайных подграфов некоторого дистанционного графа”, Пробл. передачи информ., 53:4 (2017), 3–15; Problems Inform. Transmission, 53:4 (2017), 307–318
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi2249 https://www.mathnet.ru/rus/ppi/v53/i4/p3
|
Статистика просмотров: |
Страница аннотации: | 211 | PDF полного текста: | 50 | Список литературы: | 32 | Первая страница: | 7 |
|