Parallel local search for Steiner trees in graphs

M.G.A. Verhoeven and M.E.M. Severens

Annals of Operations Research, 1999, vol. 90, issue 0, 185-202

Abstract: This paper discusses sequential and parallel local search for the Steiner tree problem ingraphs. We introduce novel neighborhoods whose computational time and space complexityis smaller than those known in the literature. We present computational results for benchmarkinstances from [3] and instances derived from real‐world traveling salesman problem instances,which contain up to 18,512 vertices and 325,093 edges. These results show that good‐qualitysolutions can be obtained in moderate running times. Furthermore, we present a parallellocal search algorithm based on multiple‐step parallelism and an optimal polynomial‐timecombination function. Computational results show that good speed‐ups can be obtainedwithout loss in quality of final solutions. Copyright Kluwer Academic Publishers 1999

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

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018908614375 (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:90:y:1999:i:0:p:185-202:10.1023/a:1018908614375

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

DOI: 10.1023/A:1018908614375

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 ().