Premium
Multicriteria path and tree problems: discussion on exact algorithms and applications
Author(s) -
Clímaco João C. N.,
Pascoal Marta M. B.
Publication year - 2012
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2011.00815.x
Subject(s) - path (computing) , tree (set theory) , computer science , mathematical optimization , minimum spanning tree , spanning tree , shortest path problem , distributed minimum spanning tree , algorithm , mathematics , theoretical computer science , graph , combinatorics , programming language , mathematical analysis
Multicriteria/multiobjective path and tree models are useful in many applications. Particularly, in Internet routing problems they seem to lead to promising approaches. In the first part of this paper, we classify and present the main exact approaches dealing with several multicriteria path problems putting in evidence the shortest path problem. In the second part, we review exact algorithms dedicated to some multicriteria tree problems, namely the minimum spanning tree and the minimum cost/minimum label spanning tree problems. Finally, the application of these models is exemplified.