Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/52586Полная запись метаданных
| Поле DC | Значение | Язык |
|---|---|---|
| dc.contributor.author | Дугинов, О. И. | - |
| dc.date.accessioned | 2013-11-20T10:39:30Z | - |
| dc.date.available | 2013-11-20T10:39:30Z | - |
| dc.date.issued | 2013 | - |
| dc.identifier.uri | http://elib.bsu.by/handle/123456789/52586 | - |
| dc.description.abstract | Изучается вычислительная сложность следующей задачи распознавания: для заданного графа и натурального k требуется ответить на вопрос: можно ли разбить множество вершин этого графа на не более чем k связных полных двудольных подграфов. Известно, что эта задача является NP-полной в классе двудольных графов. Установлено, что рассматриваемая задача является полиноми- ально разрешимой в классах двудольных дистанционно-наследуемых графов, двудольных перестановочных графов и остается NP-полной для двудольных графов с совершенным исключением, C4-свободных двудольных графов. | ru |
| dc.language.iso | ru | ru |
| dc.publisher | Минск, БГУ | ru |
| dc.subject | ЭБ БГУ::ОБЩЕСТВЕННЫЕ НАУКИ::Информатика | ru |
| dc.title | Разбиение множества вершин двудольного графа наименьшим числом полных двудольных подграфов | ru |
| dc.type | Article | ru |
| Располагается в коллекциях: | Секция 9. Теоретическая информатика | |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.