Средняя длина st (простых) путей в ориентированном графе

Учитывая тот факт , что - путь перечисления является # Р-полной задачи, может ли быть эффективные методы , которые вычисляют (или , по меньшей мере , приблизительно) средняя длина - пути без перечисления их? ~~Что если пути разрешены для пересмотра вершин?~~ $s$ $t$ $s$ $t$

Соответствующие результаты на специальных графиках также могут быть полезны.

algorithms complexity-theory graphs approximation enumeration liuyu
источник

Если путям разрешено пересматривать вершины, то непростой путь

подразумевает отсутствие средней длины, поскольку длина будет стремиться к бесконечности.

s - t

$s-t$

Шаул

@ Шал, ты прав. Я думал о ударяя время случайного блуждания от

до

. Но средняя длина имеет тенденцию к бесконечности , без дополнительных ограничений.

s

$s$

t

$t$

liuyu

это кажется очень продвинутым, рекомендую перейти на cstheory

vzn

Если я понимаю правильно, этот вопрос может представлять интерес для Вас на специальный график.

Юхо

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

путей и посмотреть на стандартном отклонении результатов.

s

$s$

t

$t$

ВЗН

Ответы: