Library

X
feed icon rss

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
    On the complexity of preflow-push algorithms for maximum-flow problems (1994)
    Springer
    Algorithmica 11 (1994), S. 353-359 
    Details
    ISSN: 1432-0541
    Keywords: Graph theory ; Network flows ; Algorithms ; Complexity ; Maximum flow
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the maximum-flow algorithm of Goldberg and Tarjan and show that the largest-label implementation runs inO(n 2 √m) time. We give a new proof of this fact. We compare our proof with the earlier work by Cheriyan and Maheswari who showed that the largest-label implementation of the preflow-push algorithm of Goldberg and Tarjan runs inO(n 2 √m) time when implemented with current edges. Our proof that the number of nonsaturating pushes isO(n 2 √m), does not rely on implementing pushes with current edges, therefore it is true for a much larger family of largest-label implementation of the preflow-push algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187018
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Characterization of the barrier parameter of homogeneous convex cones (1998)
    Springer
    Mathematical programming 81 (1998), S. 55-76 
    Details
    ISSN: 1436-4646
    Keywords: Barrier functions ; Self-concordance ; Carathéodory number ; Homogeneous cones ; Siegel domain ; Rank
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We characterize the smallest (best) barrier parameter of self-concordant barriers for homogeneous convex cones. In particular, we prove that this parameter is the same as the rank of the cone which is the number of steps in a recursive construction of the cone (Siegel domain construction). We also provide lower bounds on the barrier parameter in terms of the Carathéodory number of the cone. The bounds are tight for homogeneous self-dual cones. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584844
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...