IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v86y1999i0p321-34510.1023-a1018967121276.html
   My bibliography  Save this article

The Steiner tree problem with hop constraints

Author

Listed:
  • S. Voß

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

Suggested Citation

  • S. Voß, 1999. "The Steiner tree problem with hop constraints," Annals of Operations Research, Springer, vol. 86(0), pages 321-345, January.
    • Handle: RePEc:spr:annopr:v:86:y:1999:i:0:p:321-345:10.1023/a:1018967121276
    DOI: 10.1023/A:1018967121276
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1023/A:1018967121276
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1023/A:1018967121276?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gouveia, Luis & Requejo, Cristina, 2001. "A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem," European Journal of Operational Research, Elsevier, vol. 132(3), pages 539-552, August.
    2. Li, Xiangyong & Aneja, Y.P. & Huo, Jiazhen, 2012. "Using branch-and-price approach to solve the directed network design problem with relays," Omega, Elsevier, vol. 40(5), pages 672-679.
    3. Gouveia, Luis & Leitner, Markus & Ljubić, Ivana, 2014. "Hop constrained Steiner trees with multiple root nodes," European Journal of Operational Research, Elsevier, vol. 236(1), pages 100-112.
    4. Cabral, Edgar Alberto & Erkut, Erhan & Laporte, Gilbert & Patterson, Raymond A., 2007. "The network design problem with relays," European Journal of Operational Research, Elsevier, vol. 180(2), pages 834-844, July.
    5. Konak, Abdullah, 2012. "Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation," European Journal of Operational Research, Elsevier, vol. 218(3), pages 829-837.
    6. Nigam, Ashutosh & Agarwal, Yogesh K., 2014. "Optimal relay node placement in delay constrained wireless sensor network design," European Journal of Operational Research, Elsevier, vol. 233(1), pages 220-233.
    7. Kang, Jangha & Park, Kyungchul & Park, Sungsoo, 2009. "Optimal multicast route packing," European Journal of Operational Research, Elsevier, vol. 196(1), pages 351-359, July.
    8. Fu, Zhang-Hua & Hao, Jin-Kao, 2014. "Breakout local search for the Steiner tree problem with revenue, budget and hop constraints," European Journal of Operational Research, Elsevier, vol. 232(1), pages 209-220.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:86:y:1999:i:0:p:321-345:10.1023/a:1018967121276. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.