Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.3. Некоторые вычислительные результаты

Алгоритм для ЗНП, а следовательно, и для является хорошим алгоритмом в том смысле, что необходимое для него число операций является полиномиальной функцией от числа вершин графа. Для ЗНП требуемое для вычислений время растет хотя на практике этот рост значительно

(кликните для просмотра скана)

медленнее [30]. Программа для вычислительной машины, приведенная в [30], дает зависимость вида а другая программа [29] — зависимость вида Эдмондс и Джонсон [29] привели типичный результат для задачи о паросочетании (на самом деле — для общей задачи, обсуждавшейся в разд. 5, с или с 300 вершинами и 1500 ребрами, потребовавшей для решения около 30 секунд на .

<< Предыдущий параграф Следующий параграф >>
Оглавление