Trees and Forests - Université de technologie de Troyes Access content directly
Book Sections Year : 2016

Trees and Forests


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.
Not file

Dates and versions

hal-02291618 , version 1 (19-09-2019)


  • HAL Id : hal-02291618 , version 1


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


Gmail Facebook Twitter LinkedIn More