Parallel maximum flow solver for multi-core machines

dc.contributor	Graduate Program in Computer Engineering.
dc.contributor.advisor	Özturan, Can.
dc.contributor.author	Cihan, Selçuk.
dc.date.accessioned	2023-03-16T10:00:18Z
dc.date.available	2023-03-16T10:00:18Z
dc.date.issued	2010.
dc.identifier.other	CMPE 2010 C54
dc.identifier.uri	http://digitalarchive.boun.edu.tr/handle/123456789/12172
dc.description.abstract	We provide a parallel algorithm for calculating maximum flow between two nodes, in a capacitated network. The algorithm we propose is based on push-relabel algorithm due to Goldberg and uses a modified first in first out selection strategy together with global relabeling heuristic. Our implementation targets multi-core processors, implements task stealing to balance load between multiple threads of execution and uses fast atomic variables for synchronization instead of costly general purpose locks. We compare our algorithm to other push-relabel based algorithms and demonstrate that it performs well in practice.
dc.format.extent	30cm.
dc.publisher	Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2010.
dc.relation	Includes appendices.
dc.relation	Includes appendices.
dc.subject.lcsh	Parallel algorithms.
dc.subject.lcsh	Parallel processing (Electronic computers)
dc.subject.lcsh	Graph theory.
dc.title	Parallel maximum flow solver for multi-core machines
dc.format.pages	xiii, 58 leaves;