A Weighted Graph Partitioning Problem with Side Constraints
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...
Saved in:
| Main Authors: | , |
|---|---|
| 格式: | text |
| 語言: | English |
| 出版: |
Institutional Knowledge at Singapore Management University
1992
|
| 主題: | |
| 在線閱讀: | https://ink.library.smu.edu.sg/sis_research/1599 |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 機構: | Singapore Management University |
| 語言: | English |
| id |
sg-smu-ink.sis_research-2598 |
|---|---|
| record_format |
dspace |
| spelling |
sg-smu-ink.sis_research-25982012-10-22T05:48:24Z A Weighted Graph Partitioning Problem with Side Constraints HUM, Sin Hoon LEONG, Thin Yin 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. 1992-06-01T07:00:00Z text https://ink.library.smu.edu.sg/sis_research/1599 Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Computer Sciences Management Information Systems |
| institution |
Singapore Management University |
| building |
SMU Libraries |
| continent |
Asia |
| country |
Singapore Singapore |
| content_provider |
SMU Libraries |
| collection |
InK@SMU |
| language |
English |
| topic |
Computer Sciences Management Information Systems |
| spellingShingle |
Computer Sciences Management Information Systems HUM, Sin Hoon LEONG, Thin Yin A Weighted Graph Partitioning Problem with Side Constraints |
| description |
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. |
| format |
text |
| author |
HUM, Sin Hoon LEONG, Thin Yin |
| author_facet |
HUM, Sin Hoon LEONG, Thin Yin |
| author_sort |
HUM, Sin Hoon |
| title |
A Weighted Graph Partitioning Problem with Side Constraints |
| title_short |
A Weighted Graph Partitioning Problem with Side Constraints |
| title_full |
A Weighted Graph Partitioning Problem with Side Constraints |
| title_fullStr |
A Weighted Graph Partitioning Problem with Side Constraints |
| title_full_unstemmed |
A Weighted Graph Partitioning Problem with Side Constraints |
| title_sort |
weighted graph partitioning problem with side constraints |
| publisher |
Institutional Knowledge at Singapore Management University |
| publishDate |
1992 |
| url |
https://ink.library.smu.edu.sg/sis_research/1599 |
| _version_ |
1770571312972955648 |