Complex Systems

Neural Networks and Graph K-Partitioning Download PDF

Laurent Hérault
Jean-Jacques Niez
CEA-IRDI Division LETI/D. SYS CENG,
Avenue des Martyrs, 85X 38041 Grenoble Cedex, France

Abstract

With the emergence of neural network architectures, combinatorial optimization problems and NP-complete problems may be tackled with a new attention combining biology, physics and data processing. This paper deals with one of these problems: the graph K-partitioning. After a brief critical review of the conventional methods, we show how a particular vectorial encoding associated with this problem produces original neural network methods. Through different graph families, a comparative analysis of our approaches with one of the best conventional algorithms is developed.