The Steiner tree problem with hop constraints

S. Voß

Annals of Operations Research, 1999, vol. 86, issue 0, 345 pages

Abstract: The Steiner tree problem in graphs is to determine a minimum cost subgraph of a givengraph spanning a set of specified vertices. In certain telecommunication networks, additionalconstraints such as, e.g., reliability constraints, have to be observed. Assume that a certainreliability is associated with each arc of the network, measuring the probability that therespective arc is operational. In case there has to be a guarantee that each message sent froma root vertex to a specified vertex reaches its destination with a certain probability, so‐calledhop constraints may be used to model the respective generalization. In this paper, we discussthe Steiner tree problem with hop constraints, i.e., a generalization of Steiner's problem ingraphs where the number of arcs (hops) between a root node and any of the specified verticesis limited. A mathematical programming formulation is provided and extended to handleproblem instances of moderate size. As the Steiner tree problem with hop constraints is NP‐hard,a simple heuristic is developed and an exchange procedure based on the tabu searchmetastrategy is applied to improve given solutions. Numerical results are discussed for anumber of problem instances derived from, e.g., well‐known benchmark instances of Steiner'sproblem in graphs. Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018967121276 (text/html)
Access to full text is restricted to subscribers.

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:annopr:v:86:y:1999:i:0:p:321-345:10.1023/a:1018967121276

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018967121276

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().