Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 344437.0, MPI für Informatik / Algorithms and Complexity Group
A correctness certificate for the Stoer-Wagner min-cut algorithm
Authors:Arikati, Srinivasa Rao; Mehlhorn, Kurt
Language:English
Date of Publication (YYYY-MM-DD):1999
Title of Journal:Information Processing Letters
Volume:70
Start Page:251
End Page:254
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2008-01-04
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-E77DC5FAFF8CE44EC12568AB00367ABD-...
Full Text:
You have privileges to view the following file(s):
Mehlhorn_a_1999_a.pdf  [58,00 Kb] [Comment:file from upload service]  
 
141.pdf  [151,00 Kb] [Comment:file from upload service]  
 
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.