Skip to Main content Skip to Navigation
Book sections

Trees and Forests

Abstract : 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.
Document type :
Book sections
Complete list of metadata
Contributor : Jean-Baptiste VU VAN Connect in order to contact the contributor
Submitted on : Thursday, September 19, 2019 - 9:34:39 AM
Last modification on : Sunday, June 26, 2022 - 1:37:01 AM


  • 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⟩



Record views