Longueur moyenne des st (simples) chemins dans un graphique orienté

11

Étant donné que l' énumération du chemin - est un problème # P-complet, pourrait-il y avoir des méthodes efficaces qui calculent (ou du moins approximent) la longueur moyenne du chemin - sans les énumérer? Que faire si les chemins sont autorisés à revoir les sommets?stst

Des résultats pertinents sur des graphiques spéciaux pourraient également être utiles.

algorithms complexity-theory graphs approximation enumeration liuyu
la source
1
Si les chemins sont autorisés à revoir les sommets, un chemin non simple implique qu'il n'y a pas de longueur moyenne, car la longueur tendra à l'infini. s−t
Shaull
@Shaull, tu as raison. Je pensais au temps de frappe d'une marche aléatoire de à . Mais la longueur moyenne tend à l'infini sans autres contraintes. st
liuyu
cela semble être très avancé, recommandez de migrer vers cstheory
vzn
Si je comprends bien, cette question pourrait vous intéresser pour un graphique spécial.
Juho
1
semble que cela pourrait être lié au débit réseau maximal? notez également pour les petits graphes du monde et divers autres graphes avec une certaine symétrie, il tendra vers la longueur moyenne du chemin . un algorithme assez naturel pourrait consister à échantillonner au hasard les chemins - courts et à examiner l 'écart - type des résultats. st
vzn

Réponses:

3

le calcul / l'estimation / l'approximation de la longueur moyenne du chemin a été étudié pour certains modèles de graphiques aléatoires, y compris le modèle Erdos-Renyi et les réseaux libres à l'échelle de Barabasi-Albert, ainsi que les petits graphiques du monde Strogatz qui peuvent convenir comme approximations pour vos graphiques. [il serait préférable que vous puissiez affiner / détailler la nature / les caractéristiques des graphiques que vous étudiez.]

vzn
la source
Merci pour le commentaire et les références. J'ai rencontré ce problème en essayant de modéliser la charge de travail d'un système de traitement des requêtes avec un graphique probabiliste. Le modèle de graphe possède certaines propriétés uniques qui m'amènent à penser qu'il pourrait y avoir une approximation des chemins - longueur moyenne . Comme suggéré dans votre commentaire, l'échantillonnage aléatoire donne une approximation. Le problème est qu'il ne donne pas de limite supérieure garantie de l'approximation, sauf la longueur du plus long chemin - . Pire encore, le calcul du plus long chemin - lui-même est un problème NP-complet. ststst
liuyu