Trees and Forests

Andréa Cynthia Santos (), Christophe Duhamel () and Rafael Andrade ()
Additional contact information
Andréa Cynthia Santos: Université de Technologie de Troyes, ICD-LOSI, UMR CNRS 6281
Christophe Duhamel: Université Blaise Pascal, LIMOS-UBP, UMR CNRS 6158
Rafael Andrade: Universidade Federal do Ceará, Departamento de Estatística e Matemática Aplicada, Centro de Ciências

Chapter 46 in Handbook of Heuristics, 2018, pp 1307-1333 from Springer

Abstract: 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 metaheuristic algorithms, 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.

Keywords: bi-objective heuristic; DBMST; DCMST; forest; heuristics; Langrangian heuristic; tree (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-07124-4_49

Ordering information: This item can be ordered from
http://www.springer.com/9783319071244

DOI: 10.1007/978-3-319-07124-4_49

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().