Heuristics for graph decomposition

Mansour, N.; Dana, T.; Tabbara, H.

Heuristics for graph decomposition

Mansour, N.; Dana, T.; Tabbara, H.

URI: http://hdl.handle.net/10725/7909

URL: https://ieeexplore.ieee.org/abstract/document/912961/

DOI: http://dx.doi.org/10.1109/ICECS.2000.912961

Date: 2018-05-23

Terms of Use: This item is made available under the terms and conditions applicable to " Conference Paper / Proceeding ", as set forth at: http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php

Abstract:

The problem addressed in this paper is that of decomposing a weighted graph into a specified number of subgraphs such that these subgraphs have balanced sums of vertex weights and minimal sums of edge weights. To find a reasonable solution to this intractable problem, we suggest an approximate objective function that can be minimized by heuristic procedures. The heuristic procedure that we propose is based on a hybrid genetic algorithm (HGA) for decomposing a graph followed by an iterative improvement heuristic for tuning the HGA's results. We applied our proposed heuristics to several graphs and obtained promising results.

Citation:

Tabbara, H., Dana, T., & Mansour, N. (2000). Heuristics for graph decomposition. In Electronics, Circuits and Systems, 2000. ICECS 2000. The 7th IEEE International Conference on (Vol. 2, pp. 650-653). IEEE.