Критический путь графа

Критический путь графа — путь максимальной длины в ориентированном ациклическом графе.

Его длина является минимальной из всех возможных высот у ярусно-параллельной формы данного ациклического графа.

При аналитическом задании графа нахождение длины его критического пути как функции внешних параметров задачи является одной из важных задач при распараллеливании алгоритмов. При этом даже в случае, когда алгоритм относится к простому, например, линейному классу, заранее нельзя предугадать, к какому классу функций будет относиться длина критического пути. Скажем, существуют простые примеры, опровергающие гипотезу принадлежности этой функции к классу полиномов.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home