Исследование систем уравнений над различными классами конечных матроидов Научная публикация
| Журнал |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Вых. Данные | Год: 2022, Том: 19, Номер: 2, Страницы: 1094-1102 Страниц : 9 DOI: 10.33048/semi.2022.19.088 | ||
| Ключевые слова | graph, matroid, system of equations, computational complexity. | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Реферат:
In the paper, it is proved that the problem of checking compatibility of a finite system of equations over a matroid of rank not exeeding k is NP-complete for k ⩾ 2. Moreover, it is proved that the problem of checking compatibility of a finite system of equations over a k-uniform matroid is also NP-complete for k ⩾ 2, and the problem of checking compatibility of a finite system of equations over a partition matroid of rank not exeeding k is polynomially solvable for k = 2 and NP-complete for k ⩾ 3.
Библиографическая ссылка:
Ильев А.В.
Исследование систем уравнений над различными классами конечных матроидов
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2022. Т.19. №2. С.1094-1102. DOI: 10.33048/semi.2022.19.088 WOS РИНЦ
Исследование систем уравнений над различными классами конечных матроидов
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2022. Т.19. №2. С.1094-1102. DOI: 10.33048/semi.2022.19.088 WOS РИНЦ
Даты:
| Поступила в редакцию: | 5 нояб. 2022 г. |
| Опубликована online: | 29 дек. 2022 г. |
| Опубликована в печати: | 7 мар. 2023 г. |
Идентификаторы БД:
| Web of science: | WOS:000959099400014 |
| РИНЦ: | 50336874 |