Supposons qu'il existe plusieurs paires de destinations source dans un graphe non orienté. Je veux générer des chemins disjoints pour plusieurs paires. Quelle serait la complexité d'un tel problème? Existe-t-il une heuristique polynomiale pour trouver des chemins disjoints entre ces paires? (C.-chemin entre s1 et d1 ne doit pas présenter d'arêtes communes avec le chemin entre s2 et d2)All algorithmes de chemins disjoints au maximum
Cela ressemble à une variante du problème d'écoulement multi-produit: http://en.wikipedia.org/wiki/Multi-commodity_flow_problem
traiter chaque paire source/puits en tant que une nouvelle marchandise, et donnez à vos arêtes des poids unitaires pour appliquer des chemins disjoints. Recherchez maintenant dans la littérature les approximations de cette classe de MCFP avec les capacités unitaires.
Est-ce que ce devrait être un problème d'écoulement de multi-produits de coût minimum ou un maximum? –
Je crois que vous êtes intéressé par la faisabilité de satisfaire la demande avec des chemins disjoints. dans ce cas, les coûts (fonction objectif) ne sont pas si pertinents. Cela étant dit, j'utiliserais le coût minimum parce que cette variante a tendance à avoir de fortes exigences sur les puits –
Votre problème est NP-difficile, même dans le cas de deux sources et deux puits. Il devient polynomial résoluble si vous arrêtez de soigner quelle source correspond à quel évier.
Il existe un algorithme glouton de premier chemin le plus court proposé par Kolliopoulos et Stein. Je me demandais simplement s'il existait un meilleur algorithme d'approximation. –