Algoritmul Push-Relabel
Algoritmul Push-Relabel, dezvoltat de Andrew V. Goldberg și Robert E. Tarjan în 1988, este o metodă foarte eficientă pentru calcularea fluxului maxim în rețele. Spre deosebire de metodele bazate pe căi de augmentare, acesta menține un preflux și utilizează operații locale de 'push' (împingere) și globale de 'relabel' (reetichetare) pentru a direcționa fluxul către consumator, obținând o complexitate superioară în cel mai rău caz.
Citește metoda completă
Autentifică-te cu un cont gratuit pentru a citi această secțiune.
Method map
The neighbourhood of related methods — select a node to explore.
Surse
- Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940. DOI: 10.1145/48014.61051 ↗
- Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin. link ↗
Cum se citează această pagină
ScholarGate. (2026, June 3). Push-Relabel Algorithm for Maximum Flow. ScholarGate. https://scholargate.app/ro/operations-research/push-relabel-algorithm
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Algoritmul Bellman-FordCercetare operațională↔ compare
- Algoritmul lui DijkstraCercetare operațională↔ compare
- Algoritmul Ford-FulkersonCercetare operațională↔ compare
Citat de
Ai observat o problemă pe această pagină? Raportează sau sugerează o corectură →