Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Max Flow Algorithms: Ford-Fulkerson, Edmond-Karp, Goldberg-TarjanComparison in regards to practical running time on different types of randomized  flow networks.
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

The original algorithm proposed by Ford and Fulkerson to solve the maximum flow problem is still in use but is far from the only alternative. This paper introduces that algorithm as well as the similar Edmond-Karp and the more modern Goldberg-Tarjan.

Ford-Fulkerson uses depth-first-searches to find augmenting paths through a residual graph. Edmond-Karp instead uses breath-first-searches to achieve a polynomial time complexity. Goldberg-Tarjan solves the problem by gradually pushing flow through the residual graph.

 A comparison on randomized graphs where the size, graph density and the maximum edge capacity was varied one at a time was performed. The results show that the Goldberg-Tarjan algorithm has higher performance than the others, but only if it uses heuristics.

Place, publisher, year, edition, pages
2015.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-168027OAI: oai:DiVA.org:kth-168027DiVA: diva2:813988
Supervisors
Examiners
Available from: 2015-05-28 Created: 2015-05-25 Last updated: 2015-05-28Bibliographically approved

Open Access in DiVA

fulltext(1302 kB)309 downloads
File information
File name FULLTEXT01.pdfFile size 1302 kBChecksum SHA-512
60c811b21fca7b0edae14490757817ed9a365f4da7b0d20ddcc6e7b47f446a38b268273b4fc9c2fc9a6dd5b4841f57c7f6ac564e11071c6619b1fbf9e2b22f88
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 309 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 141 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf