A Weighted Graph Partitioning Problem with Side Constraints

• Main Authors: HUM, Sin Hoon, LEONG, Thin Yin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 1992
• Subjects: Computer Sciences; Management Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/1599
• Institution: Singapore Management University

This paper considers a weighted-graph partitioning problem with side capacity constraints and a special underlying structure: certain nodes are already preassigned to partitions of the graph. We exploit the special underlying structure to make the graph partitioning problem into a maximum flow netwo...