Algorithm 1002: Graph coloring based parallel push-relabel algorithm for the maximum flow problem


Kara G., ÖZTURAN C.

ACM Transactions on Mathematical Software, cilt.45, sa.4, 2019 (SCI-Expanded, Scopus)

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 45 Sayı: 4
  • Basım Tarihi: 2019
  • Doi Numarası: 10.1145/3330481
  • Dergi Adı: ACM Transactions on Mathematical Software
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Anahtar Kelimeler: Minimum cut problem, Preflow-push algorithm, Vertex coloring
  • Boğaziçi Üniversitesi Adresli: Evet

Özet

The maximum flow problem is one of the most common network flow problems. This problem involves finding the maximum possible amount of flow between two designated nodes on a network with arcs having flow capacities. The push-relabel algorithm is one of the fastest algorithms to solve this problem. We present a shared memory parallel push-relabel algorithm. Graph coloring is used to avoid collisions between threads for concurrent push and relabel operations. In addition, excess values of target nodes are updated using atomic instructions to prevent race conditions. The experiments show that our algorithm is competitive for wide graphs with low diameters. Results from three different data sets are included, computer vision problems, DIMACS challenge problems, and KaHIP partitioning problems. These are compared with existing pushrelabel and pseudoflow implementations. We show that high speedup rates are possible using our coloring based parallelization technique on sparse networks. However, we also observe that the pseudoflow algorithm runs faster than the push-relabel algorithm on dense and long networks.