АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ ГРАФОВЫХ ЗАДАЧ НАДЕЖНОСТИ
| dc.contributor.author | Черняк, Аркадий Александрович | |
| dc.date.accessioned | 2021-09-15T12:25:30Z | |
| dc.date.available | 2021-09-15T12:25:30Z | |
| dc.date.issued | 1999 | |
| dc.description.abstract | It is known that the problem of computing the all-terminal reliability is #.P-complete for planar graphs while being polynomially solvable for trees, series-parallel graphs and complete graphs. In this paper it is proved that the problem of computing all-terminal reliability is #P-complete for bipartite graphs of arbitrary girth and for split graphs with the regular part of degree 2. | ru_RU |
| dc.identifier.uri | http://elib.bspu.by/handle/doc/52433 | |
| dc.language.iso | other | ru_RU |
| dc.relation.ispartofseries | Весці НАН Беларусі Сер. фіз.-мат. навук;№ 1.- С. 130-135 | |
| dc.subject | графы | ru_RU |
| dc.subject | графовые задачи | ru_RU |
| dc.subject | математика | ru_RU |
| dc.title | АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ ГРАФОВЫХ ЗАДАЧ НАДЕЖНОСТИ | ru_RU |
| dc.type | Article | ru_RU |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Алгоритмическая сложность графовых задач надежности.pdf
- Size:
- 1.33 MB
- Format:
- Adobe Portable Document Format
- Description:
License bundle
1 - 1 of 1
Loading...
- Name:
- license.txt
- Size:
- 197 B
- Format:
- Item-specific license agreed upon to submission
- Description: