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

This document is currently not available here.

Share

COinS