Library

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 11 (1994), S. 278-290 
    ISSN: 1432-0541
    Keywords: Network flow ; Cuts ; Parametric cuts ; Graph algorithms ; Layout
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Galloet al. [4] recently examined the problem of computing on line a sequence ofk maximum flows and minimum cuts in a network ofn nodes, where certain edge capacities change between each flow. They showed that for an important class of networks, thek maximum flows and minimum cuts can be computed simply in O(n3+kn2) total time, provided that the capacity changes are made “in order.” Using dynamic trees their time bound isO(nm log(n2/m)+km log(n2/m)). We show how to reduce the total time, using a simple algorithm, to O(n3+kn) for explicitly computing thek minimum cuts and implicitly representing thek flows. Using dynamic trees our bound is O(nm log(n2/m)+kn log(n2/m)). We further reduce the total time toO(n 2√m) ifk is at most O(n). We also apply the ideas from [10] to show that the faster bounds hold even when the capacity changes are not “in order,” provided we only need the minimum cuts; if the flows are required then the times are respectively O(n3+km) and O(n2√m). We illustrate the utility of these results by applying them to therectilinear layout problem.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...