Исследование систем уравнений над различными классами конечных матроидов Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Output data | Year: 2022, Volume: 19, Number: 2, Pages: 1094-1102 Pages count : 9 DOI: 10.33048/semi.2022.19.088 | ||
| Tags | graph, matroid, system of equations, computational complexity. | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Abstract:
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.
Cite:
Ильев А.В.
Исследование систем уравнений над различными классами конечных матроидов
Сибирские электронные математические известия (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 РИНЦ
Dates:
| Submitted: | Nov 5, 2022 |
| Published online: | Dec 29, 2022 |
| Published print: | Mar 7, 2023 |
Identifiers:
| Web of science: | WOS:000959099400014 |
| Elibrary: | 50336874 |