Trees and Forests

Andréa Cynthia Santos (1) , Christophe Duhamel (2) , Rafael Andrade (3)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
3 UFC - Universidade Federal do Ceará = Federal University of Ceará

Trees and forests have been a fascinating research topic in Operations Research (OR)/Management Science (MS) throughout the years because they are involved in numerous difficult problems, have interesting theoretical properties, and cover a large number of practical applications. A tree is a finite undirected connected simple graph with no cycles, while a set of independent trees is called a forest. A spanning tree is a tree covering all nodes of a graph. In this chapter, key components for solving difficult tree and forest problems, as well as insights to develop efficient heuristics relying on such structures, are surveyed. They are usually combined to obtain very efficient metaheuristics, hybrid methods, and matheuristics. Some emerging topics and trends in trees and forests are pointed out. This is followed by two case studies: a Lagrangian-based heuristic for the minimum degree-constrained spanning tree problem and an evolutionary algorithm for a generalization of the bounded-diameter minimum spanning tree problem. Both problems find applications in network design, telecommunication, and transportation fields, among others.

Domaines: Recherche opérationnelle [math.OC]

Andréa Cynthia Santos, Christophe Duhamel, Rafael Andrade. Trees and Forests. Handbook of Heuristics, Springer International Publishing, pp.1-27, 2016. ⟨hal-02291618⟩