Отрывок: Теорема. Если все графы переходов принадлежат либо классу пол- ных многодольных графов, либо классу паросочетаний, то задача построе- ния -совместимой цепи является разрешимой за время . В против- ном случае данная задача является -полной. Известны алгоритмы, позволяющие решить указанные задачи за полино- миальное время [7, 8]. В частности, задачу (1) можно решить за линейное вре- мя, задачи (2) и (3) – за время . Для решения задачи (1) при выполн...
Полная запись метаданных
Поле DC | Значение | Язык |
---|---|---|
dc.contributor.author | Макаровских, Т. А. | - |
dc.date.accessioned | 2018-07-09 11:50:51 | - |
dc.date.available | 2018-07-09 11:50:51 | - |
dc.date.issued | 2018-04 | - |
dc.identifier | Dspace\SGAU\20180709\70647 | ru |
dc.identifier.citation | Перспективные информационные технологии (ПИТ 2018) [Электронный ресурс]: труды Международной научно-технической конференции / под ред. С.А. Прохорова. – Электрон. текстовые и граф. дан. (34,4 Мбайт). – Самара: Издательство Самарского научного центра РАН, 2018. – С. 831-835 | ru |
dc.identifier.issn | 978-5-93424-817-9 | - |
dc.identifier.uri | http://repo.ssau.ru/handle/Perspektivnye-informacionnye-tehnologii/Sposob-resheniya-zadachi-marshrutizacii-na-osnove-postroeniya-pokrytii-v-ploskih-grafah-70647 | - |
dc.language.iso | rus | ru |
dc.publisher | Издательство Самарского научного центра РАН | ru |
dc.title | Способ решения задачи маршрутизации на основе построения покрытий в плоских графах | ru |
dc.type | Article | ru |
dc.textpart | Теорема. Если все графы переходов принадлежат либо классу пол- ных многодольных графов, либо классу паросочетаний, то задача построе- ния -совместимой цепи является разрешимой за время . В против- ном случае данная задача является -полной. Известны алгоритмы, позволяющие решить указанные задачи за полино- миальное время [7, 8]. В частности, задачу (1) можно решить за линейное вре- мя, задачи (2) и (3) – за время . Для решения задачи (1) при выполн... | - |
dc.classindex.udc | 004 | - |
Располагается в коллекциях: | Перспективные информационные технологии |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
Способ решения задачи маршрутизации на основе построения покрытий в плоских графах.pdf | 569.28 kB | Adobe PDF | Просмотреть/Открыть |
Показать базовое описание ресурса
Просмотр статистики
Поделиться:
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.