Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/52586| Заглавие документа: | Разбиение множества вершин двудольного графа наименьшим числом полных двудольных подграфов |
| Авторы: | Дугинов, О. И. |
| Тема: | ЭБ БГУ::ОБЩЕСТВЕННЫЕ НАУКИ::Информатика |
| Дата публикации: | 2013 |
| Издатель: | Минск, БГУ |
| Аннотация: | Изучается вычислительная сложность следующей задачи распознавания: для заданного графа и натурального k требуется ответить на вопрос: можно ли разбить множество вершин этого графа на не более чем k связных полных двудольных подграфов. Известно, что эта задача является NP-полной в классе двудольных графов. Установлено, что рассматриваемая задача является полиноми- ально разрешимой в классах двудольных дистанционно-наследуемых графов, двудольных перестановочных графов и остается NP-полной для двудольных графов с совершенным исключением, C4-свободных двудольных графов. |
| URI документа: | http://elib.bsu.by/handle/123456789/52586 |
| Располагается в коллекциях: | Секция 9. Теоретическая информатика |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.