Efficient algorithms for network design

• Grant number: 05/01832-3
• Support Opportunities: Regular Research Grants
• Start date: December 01, 2005
• End date: February 29, 2008
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computer Systems
• Principal Investigator: Alexandre Cláudio Botazzo Delbem
• Grantee: Alexandre Cláudio Botazzo Delbem
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

Network design problems involves several engineering and scientific fields. Computer networks, electrical circuits, routing problems, and phylogenetic trees are typical examples. In general, the network desing problems are NP-Hard. In order to deal with their complexity, alternative approaches have been developed. Evolutionary-based approaches have been proposed and shown relevant results. Nevertheless, graph encoding is critical for the performance of these algorithms for network desing problems. Aiming to overcome this difficulty, we propose the investigation of computationally efficient encodings for evolutionary algorithms for network design. (AU)