A Weighted Graph Partitioning Problem with Side Constraints
Publication Type
Conference Paper
Publication Date
6-1992
Abstract
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 network problem with side constraints. We propose an algorithm for solving our problem based on the generic version of the preflow-push algorithm for the maximum flow network problem. Also, our algorithm incorporates heuristic approaches to generate close to optimal solutions which are also feasible with regards to the side capacity constraints.
Discipline
Computer Sciences | Management Information Systems
Research Areas
Information Systems and Management
Publication
International Conference on Optimization: Techniques and Applications (ICOTA92)
Editor
Phua, K. H.; et al
First Page
235
Last Page
240
Publisher
World Scientific
City or Country
Singapore
Citation
HUM, Sin Hoon and LEONG, Thin Yin.
A Weighted Graph Partitioning Problem with Side Constraints. (1992). International Conference on Optimization: Techniques and Applications (ICOTA92). 235-240.
Available at: https://ink.library.smu.edu.sg/sis_research/1599