Skip to page content
USDA Forest Service
  
Treesearch

Research & Development Treesearch

 
Treesearch Home
About Treesearch
Contact Us
Research & Development
Forest Products Lab
International Institute of Tropical Forestry
Northern
Pacific Northwest
Pacific Southwest
Rocky Mountain
Southern Research Station
Help
 

GeoTreesearch


Science.gov - We Participate


USA.gov  Government Made Easy


Global Forest Information Service

US Forest Service
P.O. Box 96090
Washington, D.C.
20090-6090

(202) 205-8333

You are here: Home / Search / Publication Information
Bookmark and Share

Publication Information

(482 KB)

Title: The Steiner Multigraph Problem: Wildlife corridor design for multiple species

Author: Lai, Katherine J.; Gomes, Carla P.; Schwartz, Michael K.; McKelvey, Kevin S.; Calkin, David E.; Montgomery, Claire A.

Date: 2011

Source: In: Burgard, W.; Roth, D., eds. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11); San Francisco, CA, USA; August 7-11, 2011. AAAI Press. 8 p.

Publication Series: Paper (invited, offered, keynote)

Description: The conservation of wildlife corridors between existing habitat preserves is important for combating the effects of habitat loss and fragmentation facing species of concern. We introduce the Steiner Multigraph Problem to model the problem of minimum-cost wildlife corridor design for multiple species with different landscape requirements. This problem can also model other analogous settings in wireless and social networks. As a generalization of Steiner forest, the goal is to find a minimum-cost subgraph that connects multiple sets of terminals. In contrast to Steiner forest, each set of terminals can only be connected via a subset of the nodes. Generalizing Steiner forest in this way makes the problem NP-hard even when restricted to two pairs of terminals. However, we show that if the node subsets have a nested structure, the problem admits a fixed-parameter tractable algorithm in the number of terminals.We successfully test exact and heuristic solution approaches on a wildlife corridor instance for wolverines and lynx in western Montana, showing that though the problem is computationally hard, heuristics perform well, and provably optimal solutions can still be obtained.

Keywords: computational sustainability, wildlife corridors, constraint optimization, Steiner forest

Publication Notes:

  • We recommend that you also print this page and attach it to the printout of the article, to retain the full citation information.
  • This article was written and prepared by U.S. Government employees on official time, and is therefore in the public domain.
  • You may send email to rmrspubrequest@fs.fed.us to request a hard copy of this publication. (Please specify exactly which publication you are requesting and your mailing address.)

XML: View XML

Citation:


Lai, Katherine J.; Gomes, Carla P.; Schwartz, Michael K.; McKelvey, Kevin S.; Calkin, David E.; Montgomery, Claire A. 2011. The Steiner Multigraph Problem: Wildlife corridor design for multiple species. In: Burgard, W.; Roth, D., eds. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11); San Francisco, CA, USA; August 7-11, 2011. AAAI Press. 8 p.

 


 [ Get Acrobat ]  Get the latest version of the Adobe Acrobat reader or Acrobat Reader for Windows with Search and Accessibility

USDA logo which links to the department's national site. Forest Service logo which links to the agency's national site.