|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Вычислительная сложность задачи аппроксимации графовстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Авторы: Агеев А.А., Ильев В.П., Кононов А.В., Талевнин А.С.
- Журнал: Дискретный анализ и исследование операций
- Том: 13
- Номер: 1
- Год издания: 2006
- Издательство: Изд-во Ин-та математики
- Местоположение издательства: Новосибирск
- Первая страница: 3
- Последняя страница: 15
- Аннотация: Исследуется вычислительная сложность известной задачи аппроксимации графов. Показано, что различные варианты этой задачи являются NP-трудными как для неориентированных, так и для ориентированных графов. Для одного варианта задачи доказано существование полиномиальной приближённой схемы.
- Добавил в систему: Кононов Александр Вениаминович