DocumentCode
2988351
Title
Heuristics for graph decomposition
Author
Tabbara, Hiba ; Dana, Tarek ; Mansour, Nashat
Author_Institution
Comput. Sci. Program, Lebanese American Univ., Beirut, Lebanon
Volume
2
fYear
2000
fDate
2000
Firstpage
650
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
Keywords
genetic algorithms; graph theory; iterative methods; approximate objective function; balanced sums; edge weights; graph decomposition; heuristic procedures; hybrid genetic algorithm; iterative improvement heuristic; subgraphs; vertex weights; weighted graph; Biological cells; Computational modeling; Computer science; Electronic mail; Genetic algorithms;
fLanguage
English
Publisher
ieee
Conference_Titel
Electronics, Circuits and Systems, 2000. ICECS 2000. The 7th IEEE International Conference on
Conference_Location
Jounieh
Print_ISBN
0-7803-6542-9
Type
conf
DOI
10.1109/ICECS.2000.912961
Filename
912961
Link To Document