Les arbres coupés par liens sont-ils déjà utilisés dans la pratique, pour le calcul du débit maximal ou d'autres applications?

20

De nombreux algorithmes de flux max que je vois couramment implémentés, l'algorithme de Dinic, le réétiquetage push et d'autres, peuvent voir leur coût asymptotique en temps amélioré grâce à l'utilisation d' arbres dynamiques (également appelés arbres coupés de liens).

  • Push relabel s'exécute en ou ou normalement, mais avec des arbres dynamiquesO ( V 3 ) O ( V 2 √O(V2E)O(V3)O(VElog(V2/E))O(V2E)O(VElog⁡(V2/E))
  • L'algorithme de Dinic fonctionne en , mais avec des arbres dynamiquesO ( V E log ( V ) )O(V2E)O(VElog⁡(V))

Cependant, les implémentations pratiques des algorithmes max-flow dans la plupart des bibliothèques ne semblent pas utiliser cette structure de données. Les arbres dynamiques sont-ils déjà utilisés dans la pratique pour le calcul du débit maximal? Ou ont-ils trop de frais généraux pour être utiles pour les problèmes réels?

Y a-t-il d'autres domaines problématiques où des arbres coupés de liens sont utilisés?

Cette question est liée à une question que j'ai posée sur cstheory: Certains des algorithmes de débit maximal de pointe sont-ils pratiques?

reference-request graphs data-structures network-flow Rob Lachlan
la source
aperçu / desc des liens coupés mais seuls les états "sont utiles pour des applications telles que Network Flow"
vzn
d'après l'enquête tarjan citée par reza, les algorithmes de temps linéaires fonctionnent très bien / mieux pour un nombre modéré de sommets / arêtes, puis il y a un seuil de sommets / arêtes plus grands où les algorithmes logarithmiques surpassent l'algorithme linéaire. les fns d'accès logarithmique sont donc utiles et peuvent être nettement meilleurs pour les très gros graphiques.
vzn

Réponses:

7

Il existe un document intitulé " Dynamic Trees in Practice " qui passe en revue la mise en œuvre pratique.

Les autres catégories que l'arborescence Link-Cut pourrait être utilisée efficacement se trouvent dans l' indexation de base de données . Vous pouvez le trouver dans le livre " Database Index Techniques ".

Reza
la source
pense que cela nécessite une élaboration. les arbres sont utiles pour les index en général bien sûr mais dans quelles conditions l'arbre serait-il modifié?
vzn
@vzn: arbre B +, arbre R, arbre H et arbre X en sont quelques exemples.
Reza
bien sûr, mais soupçonne que personne n'a peut-être essayé d'utiliser des arbres coupés de liens dans les index DB jusqu'à présent. C'est une application plausible, mais il ne semble pas clair qu'ils soient optimisés pour les mêmes opérations que celles qui se produisent dans les index DB.
vzn
5

cet article conclut à la fin qu'un arbre de coupure de lien (LC) surpasse les arbres de râteau-compression (RC) pour l'algorithme de flux maximal Sleator / Tarjan en utilisant un générateur de graphe aléatoire Dimacs standard.

l'article se concentre sur la propagation du changement comme une application des arbres dynamiques. Par exemple, la propagation des modifications est similaire à la façon dont les cellules de tableur Excel doivent être recalculées sur les modifications apportées à certaines cellules en fonction des dépendances cellule / formule. les auteurs ont publié leur code sous forme de bibliothèque ouverte.

Une analyse expérimentale de la propagation du changement dans les arbres dynamiques Acar, Blelloch, Vittes

La propagation des modifications est une technique permettant d'ajuster automatiquement la sortie d'un algorithme aux modifications de l'entrée. L'idée derrière la propagation du changement est de suivre les dépendances entre les données et les appels de fonction, de sorte que, lorsque l'entrée change, les fonctions affectées par ce changement peuvent être réexécutées pour mettre à jour le calcul et la sortie. Le changement de propagation permet à un compilateur de dynamiser des algorithmes statiques.

vzn
la source
Je vous remercie. C'est agréable de voir quelques repères d'algorithmes impliquant des arbres dynamiques.
Rob Lachlan