Efficient Maximum Flow Algorithms.
The article discusses basic techniques concerning maximum flow algorithms that have applications in science and engineering. Topics addressed include distinctions between polynomial and strongly polynomial flow algorithms, polynomial-time algorithms resulting from the idea of augmenting along the sh...
| Publicado en: | Communications of the ACM Vol. 57; no. 8; pp. 82 - 90 |
|---|---|
| Autores principales: | , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Aug2014
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=97331017&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 97331017 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Aug2014 vid: 57 iid: 8 pid: 68 pub: Association for Computing Machinery artinfo: ui: 97331017 10.1145/2628036 ppf: 82 ppct: 8 formats: tig: atl: Efficient Maximum Flow Algorithms. aug: au: GOLDBERG, ANDREW V. TARJAN, ROBERT E. affil: Principal researcher, Microsoft Research Silicon Valley Lab, Mountain View, CA. James S. McDonnell Distinguished University Professor of Computer Science, Princeton University, Princeton, NJ Visiting researcher, Microsoft Research Silicon Valley Lab, Mountain View, CA. su: Polynomial time algorithms Algorithms Data structures Computational complexity Computable functions Computer input design sug: subj: Polynomial time algorithms Algorithms Data structures Computational complexity Computable functions Computer input design ab: The article discusses basic techniques concerning maximum flow algorithms that have applications in science and engineering. Topics addressed include distinctions between polynomial and strongly polynomial flow algorithms, polynomial-time algorithms resulting from the idea of augmenting along the shortest paths, and faster algorithms developed from data structures and fine-grain operations. Also mentioned are improving time bounds by discriminating on the basis of residual capacities when allocating arc lengths, descriptions of intuitive algorithms, and preflows used in the push-relabel method. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2014 holdings: @attributes: islocal: N |
|---|