Steiner tree problem with hop constraints

• Grant number: 11/15839-0
• Support Opportunities: Scholarships in Brazil - Master
• Start date: March 01, 2012
• End date: July 31, 2012
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Alysson Machado Costa
• Grantee: Murilo Soares Pinheiro
• 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

We are interested in the Hop-constrained Steiner tree problem (HSTP), a generalization of the classical Steiner tree problem in which additional constraints limit the number of edges in the solution in the paths connecting any given node to a root node. The HSTP has theoretical and practical interests, for it is a combinatorial problem with high complexity which models a number of real-life situations. We will review and propose linear formulations modeling the hop constraints and study the problem's polyhedral structure.