A Multiagent Algorithm for Graph Partitioning

Autor:	Francesc Comellas, Emili Sapena
Rok vydání:	2006
Předmět:	Computer science Heuristic Maximum cut Evolutionary algorithm Graph partition Voltage graph Mixed graph Graph theory Strength of a graph Graph Graph bandwidth Cut Partition (number theory) Graph (abstract data type) Level structure Closure problem NP-complete Algorithm Moral graph
Zdroj:	Lecture Notes in Computer Science ISBN: 9783540332374 EvoWorkshops
Popis:	The k-cut problem is an NP-complete problem which consists of finding a partition of a graph into k balanced parts such that the number of cut edges is minimized. Different algorithms have been proposed for this problem based on heuristic, geometrical and evolutionary methods. In this paper we present a new simple multiagent algorithm, ants, and we test its performance with standard graph benchmarks. The results show that this method can outperform several current methods while it is very simple to implement.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::51e1d8cce793888187775f653b45923a https://doi.org/10.1007/11732242_25 Zobrazit plný text záznamu