Local search for Steiner tree problems in graphs

M.G.A. Verhoeven, M.E.M. Severens, E.H.L. Aarts

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

Abstract

We present a local search algorithm for the Steiner tree problem in graphs, which uses a neighbourhood in which paths in a steiner tree are exchanged. The exchange function of this neigbourhood is based on multiple-source shortest path algorithm. We present computational results for a known benchmark set of generated Steiner tree problem instances and for a set of instances derived from the real-world travelling salesman probelm instances containing up to 18512 vertices. The results show that good quality solutions can be obtained in moderate running times.
Original languageEnglish
Title of host publicationModern Heuristic Search Methods
Place of PublicationChichester
PublisherWiley
Pages117-129
Number of pages13
ISBN (Print)0-471-96280-5
Publication statusPublished - 1996
Externally publishedYes

Cite this

Verhoeven, M. G. A., Severens, M. E. M., & Aarts, E. H. L. (1996). Local search for Steiner tree problems in graphs. In Modern Heuristic Search Methods (pp. 117-129). Chichester: Wiley.
Verhoeven, M.G.A. ; Severens, M.E.M. ; Aarts, E.H.L. / Local search for Steiner tree problems in graphs. Modern Heuristic Search Methods. Chichester : Wiley, 1996. pp. 117-129
@inbook{0e2895ff7545449cadb68971c6fb3576,
title = "Local search for Steiner tree problems in graphs",
abstract = "We present a local search algorithm for the Steiner tree problem in graphs, which uses a neighbourhood in which paths in a steiner tree are exchanged. The exchange function of this neigbourhood is based on multiple-source shortest path algorithm. We present computational results for a known benchmark set of generated Steiner tree problem instances and for a set of instances derived from the real-world travelling salesman probelm instances containing up to 18512 vertices. The results show that good quality solutions can be obtained in moderate running times.",
author = "M.G.A. Verhoeven and M.E.M. Severens and E.H.L. Aarts",
year = "1996",
language = "English",
isbn = "0-471-96280-5",
pages = "117--129",
booktitle = "Modern Heuristic Search Methods",
publisher = "Wiley",

}

Verhoeven, MGA, Severens, MEM & Aarts, EHL 1996, Local search for Steiner tree problems in graphs. in Modern Heuristic Search Methods. Wiley, Chichester, pp. 117-129.

Local search for Steiner tree problems in graphs. / Verhoeven, M.G.A.; Severens, M.E.M.; Aarts, E.H.L.

Modern Heuristic Search Methods. Chichester : Wiley, 1996. p. 117-129.

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

TY - CHAP

T1 - Local search for Steiner tree problems in graphs

AU - Verhoeven, M.G.A.

AU - Severens, M.E.M.

AU - Aarts, E.H.L.

PY - 1996

Y1 - 1996

N2 - We present a local search algorithm for the Steiner tree problem in graphs, which uses a neighbourhood in which paths in a steiner tree are exchanged. The exchange function of this neigbourhood is based on multiple-source shortest path algorithm. We present computational results for a known benchmark set of generated Steiner tree problem instances and for a set of instances derived from the real-world travelling salesman probelm instances containing up to 18512 vertices. The results show that good quality solutions can be obtained in moderate running times.

AB - We present a local search algorithm for the Steiner tree problem in graphs, which uses a neighbourhood in which paths in a steiner tree are exchanged. The exchange function of this neigbourhood is based on multiple-source shortest path algorithm. We present computational results for a known benchmark set of generated Steiner tree problem instances and for a set of instances derived from the real-world travelling salesman probelm instances containing up to 18512 vertices. The results show that good quality solutions can be obtained in moderate running times.

M3 - Chapter

SN - 0-471-96280-5

SP - 117

EP - 129

BT - Modern Heuristic Search Methods

PB - Wiley

CY - Chichester

ER -

Verhoeven MGA, Severens MEM, Aarts EHL. Local search for Steiner tree problems in graphs. In Modern Heuristic Search Methods. Chichester: Wiley. 1996. p. 117-129