Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Performance Evaluation of Parfois Retailing Stores Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Computational Comparison of Algorithms for a Generalization of the Node-Weighted Steiner Tree and Forest Problems

Authors : Raul Brás, J. Orestes Cerdeira

Published in: Operational Research

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Habitat fragmentation is a serious threat for the sustainability of species. Thus, the identification of effective linkages to connect valuable ecological units is an important issue in conservation biology. The design of effective linkages should take into account that areas which are adequately permeable for some species’ dispersal may act as obstructions for other species. The determination of minimum cost effective linkages is a generalization of both node-weighted Steiner tree and node-weighted Steiner forest problems. We compare the performance of different procedures for this problem using large real and simulated instances.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Cell-Free Layer Measurements in a Network with Bifurcating Microchannels Using a Global Approach
next chapter Development of a Numerically Efficient Biodiesel Decanter Simulator
Literature
1.
Alagador, D., Triviño, M., Cerdeira, J.O., Brás, R., Cabeza, M., Araújo, M.B.: Linking like with like: optimizing connectivity between environmentally-similar habitats. Landsc. Ecol. 27(2), 291–301 (2012)CrossRef
2.
3.
Brás, R., Cerdeira, J.O., Alagador, D., Araújo, M.B.: Linking habitats for multiple species. Env. Model. Softw. 40, 336–339 (2013)CrossRef
4.
Brooks, T.M., Mittermeier, R.A., Mittermeier, C.G., Rylands, A.B., da Fonseca, G.A.B., Konstant, W.R., Flick, P., Pilgrim, J., Oldfield, S., Magin, G., Hilton-Taylor, C.: Habitat loss and extinction in the hotspots of biodiversity. Conserv. Biol. 16, 909–923 (2002)CrossRef
5.
Demaine, E., Hajiaghayi, M., Klein, P.: Node-weighted steiner tree and group steiner tree in planar graphs. In: Albers, S., et al. (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 5555, pp. 328–340. Springer, Berlin/Heidelberg (2009)CrossRef
6.
7.
8.
9.
10.
Hanski, I.: The Shrinking World: Ecological Consequences of Habitat Loss. Excellence in Ecology, vol. 14. International Ecology Institute, Oldendorf/Luhe (2005)
11.
Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19(1), 104–115 (1995)MATHMathSciNetCrossRef
12.
13.
Lai, K.J., Gomes, C.P., Schwartz, M.K., McKelvey, K.S., Calkin, D.E., Montgomery, C.A.: The Steiner multigraph problem: wildlife corridor design for multiple species. In: Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, vol. 2, pp. 1357–1364 (2011)
14.
Magnanti, T.L., Raghavan, S.: Strong formulations for network design problems with connectivity requirements. Networks 45(2), 61–79 (2005)MATHMathSciNetCrossRef
15.
Merriam, G.: Connectivity: a fundamental ecological characteristic of landscape pattern. In: Brandt, J., Agger, P. (eds.) Proceedings of the 1st International Seminar on Methodology in Landscape Ecological Research and Planning, pp. 5–15. Roskilde University, Denmark (1984)
16.
Rayward-Smith, V.J.: The computation of nearly minimal Steiner trees in graphs. Int. J. Math. Educ. Sci. Technol. 14(1), 15–23 (1983)MATHMathSciNetCrossRef
17.
18.
19.
Siek, J.G., Lee, L., Lumsdaine, A.: The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Longman, Boston (2002)
20.
21.
Wong, R.: A dual ascent approach for Steiner tree problems on a directed graph. Math. Progr. 28, 271–287 (1984)MATHCrossRef
Metadata
Title
Computational Comparison of Algorithms for a Generalization of the Node-Weighted Steiner Tree and Forest Problems
Authors
Raul Brás
J. Orestes Cerdeira
Copyright Year
2015
Book
Operational Research

Print ISBN: 978-3-319-20327-0

Electronic ISBN: 978-3-319-20328-7

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-20328-7_5