skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

A new approach to the maximum-flow problem

Goldberg, Andrew ; Tarjan, Robert

Journal of the ACM, 1988-10, Vol.35 (4), p.921-940 [Periódico revisado por pares]

New York, NY: ACM

Texto completo disponível

Citações Citado por
  • Título:
    A new approach to the maximum-flow problem
  • Autor: Goldberg, Andrew ; Tarjan, Robert
  • Assuntos: Algorithms ; Applied sciences ; Automotive components ; Density ; Exact sciences and technology ; Flows in networks. Combinatorial problems ; Graphs ; Networks ; Operational research and scientific management ; Operational research. Management science ; Processors ; Running in ; Shortest-path problems
  • É parte de: Journal of the ACM, 1988-10, Vol.35 (4), p.921-940
  • Notas: ObjectType-Article-1
    SourceType-Scholarly Journals-1
    ObjectType-Feature-2
    content type line 23
    ObjectType-Article-2
    ObjectType-Feature-1
  • Descrição: All previously known efficient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the preflow concept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense graphs, achieving an O ( n 3 ) time bound on an n -vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running in O ( nm log( n 2 / m )) time on an n -vertex, m -edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efficient distributed and parallel implementations. A parallel implementation running in O ( n 2 log n ) time using n processors and O ( m ) space is obtained. This time bound matches that of the Shiloach-Vishkin algorithm, which also uses n processors but requires O ( n 2 ) space.
  • Editor: New York, NY: ACM
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.