• DocumentCode
    2356616
  • Title

    Maximum (s,t)-flows in planar networks in O(|V|log|V|) time

  • Author

    Weihe, Karsten

  • Author_Institution
    Fakultat fur Math., Konstanz Univ., Germany
  • fYear
    1994
  • fDate
    20-22 Nov 1994
  • Firstpage
    178
  • Lastpage
    189
  • Abstract
    Let G=(V, A) be a directed, planar graph, let s, t ∈ V, s≠t, and let ca>0 be the capacity of an arc a∈A. The problem is to find a maximum flow from s to t in G: subject to these capacities. The fastest algorithm known so far requires 𝒪(|V|·3√|V|·log|V|) time, whereas the algorithm introduced in this paper requires only 𝒪(|V|log|V|) time
  • Keywords
    computational geometry; directed graphs; flow graphs; tree data structures; directed graphs; maximum (s,t)-flows; maximum flow; planar graph; planar networks; tree data structures; Algorithm design and analysis; Intelligent networks; Shortest path problem; Telecommunication traffic; Tree data structures; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
  • Conference_Location
    Santa Fe, NM
  • Print_ISBN
    0-8186-6580-7
  • Type

    conf

  • DOI
    10.1109/SFCS.1994.365695
  • Filename
    365695
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2356616