Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Cheriyan, Joseph
Mehlhorn, Kurt

dblp
dblp



BibTeX cite key*:

Cheriyan-Mehlhorn99

Title

Title*:

An analysis of the highest-level selection rule in the preflow-push max-flow algorithm

Journal

Journal Title*:

Information Processing Letters

Journal's URL:


Download URL
for the article:

http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6V0F-3WM4NP1-5-5&_cdi=5645&_user=43521&_orig=search&_coverDate=03%2F12%2F1999&_qd=1&_sk=999309994&view=c&_alid=440632630&_rdoc=1&wchp=dGLbVzz-zSkWz&md5=3bb66a86cd6a78a464c3046a3edbab0a&ie=/sdarticle.pdf

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

69

Number:

5

Publishing Date:

1999

Pages*:

239-242

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:

10.1016/S0020-0190(99)00019-8

Note, Abstract, ©

Note:


(LaTeX) Abstract:

Consider the problem of finding a maximum flow in a network. Goldberg and Tarjan introduced the preflow-push method for solving this problem. When this method is implemented with the highest-level selection rule, then both the running time and the number of pushes are known to be Image, where n is the number of nodes and m is the number of edges. We give a new proof based on a potential function argument. Potential function arguments may be preferable for analyzing preflow-push algorithms, since they are simple and generic.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:

http://dblp.uni-trier.de/db/journals/ipl/ipl69.html#CheriyanM99

Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:

@ARTICLE{Cheriyan-Mehlhorn99,
AUTHOR = {Cheriyan, Joseph and Mehlhorn, Kurt},
TITLE = {An analysis of the highest-level selection rule in the preflow-push max-flow algorithm},
JOURNAL = {Information Processing Letters},
PUBLISHER = {Elsevier},
YEAR = {1999},
NUMBER = {5},
VOLUME = {69},
PAGES = {239--242},
DOI = {10.1016/S0020-0190(99)00019-8},
}


Entry last modified by Anja Becker, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Evelyn Haak
Created
04/15/1999 11:14:05 AM
Revisions
11.
10.
9.
8.
7.
Editor(s)
Anja Becker
Tamara Hausmann
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
04.01.2008 12:37:42
09.11.2006 14:26:57
04.10.2006 10:24:00
11.09.2006 09:58:46
01.09.2006 11:01:22