Divide-and-conquer minimal-cut bisectioning of task graphs

Sam Lor, Hong Shen, Piyush Maheshwari

Research output: Contribution to journalArticlepeer-review


This paper proposes a method for partitioning the vertex set of an undirected simple weighted graph into two subsets so as to minimise the difference of vertex-weight sums between the two subsets and the total weight of edges cut (i.e. edges with one end in each subset). The proposed heuristic algorithm works in a divide-and-conquer fashion and is a modification of an algorithm suggested in the literature. The algorithm has the same time complexity as the previous one hut is extended to work on weighted graphs.

Original languageEnglish
Pages (from-to)227-234
Number of pages8
JournalComputer Systems Science and Engineering
Issue number4
Publication statusPublished - Jul 1996
Externally publishedYes


  • Combinatorial problems
  • Graph partitioning
  • Heuristic algorithms
  • Mapping problem
  • Parallel processing


Dive into the research topics of 'Divide-and-conquer minimal-cut bisectioning of task graphs'. Together they form a unique fingerprint.

Cite this