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):

Arikati, Srinivasa Rao
Mehlhorn, Kurt

dblp
dblp



BibTeX cite key*:

Arikati-Mehlhorn

Title

Title*:

A correctness certificate for the Stoer-Wagner min-cut algorithm


Mehlhorn_a_1999_a.pdf (58.86 KB); 141.pdf (151.57 KB)

Journal

Journal Title*:

Information Processing Letters

Journal's URL:


Download URL
for the article:

http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6V0F-3X52WPC-9-9&_cdi=5645&_user=43521&_orig=search&_coverDate=06%2F21%2F1999&_qd=1&_sk=999299994&view=c&_alid=440249858&_rdoc=1&wchp=dGLzVlz-zSkzk&md5=d4831d9be655cf09e7d0cb7d53ece6ad&ie=/sdarticle.pdf

Language:

English

Publisher

Publisher's
Name:

Elesevier

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

70

Number:

5

Publishing Date:

1999

Pages*:

251-254

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:

10.1016/S0020-0190(99)00071-X

Note, Abstract, ©

Note:


(LaTeX) Abstract:

The Stoer–Wagner algorithm computes a minimum cut in a weighted undirected graph. The algorithm works in n−1 phases, where n is the number of nodes of G. Each phase takes time O(m+nlogn), where m is the number of edges of G, and computes a pair of vertices s and t and a minimum cut separating s and t. We show how to extend the algorithm such that each phase also computes a maximum flow from s to t. The flow is computed in O(m) additional time and certifies the cut computed in the phase.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:

http://dblp.uni-trier.de/db/journals/ipl/ipl70.html#ArikatiM99
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V0F-3X52WPC-9&_coverDate=06%2F21%2F1999&_alid=440249858&_rdoc=1&_fmt=&_orig=search&_qd=1&_cdi=5645&_sort=d&view=c&_acct=C000004638&_version=1&_urlVersion=0&_userid=43521&md5=6df6f2c73fbdda5077dcb6ed45731c2c

Copyright Message:


Personal Comments:


Download
Access Level:

Public

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{Arikati-Mehlhorn,
AUTHOR = {Arikati, Srinivasa Rao and Mehlhorn, Kurt},
TITLE = {A correctness certificate for the {Stoer-Wagner} min-cut algorithm},
JOURNAL = {Information Processing Letters},
PUBLISHER = {Elesevier},
YEAR = {1999},
NUMBER = {5},
VOLUME = {70},
PAGES = {251--254},
DOI = {10.1016/S0020-0190(99)00071-X},
}


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)
Ingrid Finkler
Created
03/23/2000 10:55:03 AM
Revisions
12.
11.
10.
9.
8.
Editor(s)
Anja Becker
Tamara Hausmann
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
04.01.2008 13:05:05
09.11.2006 14:27:28
04.10.2006 10:21:17
25.09.2006 11:34:39
01.09.2006 14:50:19
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
141.pdfMehlhorn_a_1999_a.pdf
View attachments here: