Reduction techniques for the prize collecting Steiner tree problem and the maximum-weight connected subgraph problem
Rehfeldt, D; Koch, T; Maher, SJ
Date: 26 October 2018
Journal
Networks
Publisher
Wiley
Publisher DOI
Abstract
The concept of reduction has frequently distinguished itself as a pivotal ingredient
of exact solving approaches for the Steiner tree problem in graphs. In this article we
broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various ...
The concept of reduction has frequently distinguished itself as a pivotal ingredient
of exact solving approaches for the Steiner tree problem in graphs. In this article we
broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical
applications: The prize-collecting Steiner tree problem, the rooted prize-collecting
Steiner tree problem and the maximum-weight connected subgraph problem. By
introducing and subsequently deploying numerous new reduction methods, we are
able to drastically decrease the size of a large number of benchmark instances,
already solving more than 90% of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the
state-of-the-art Steiner problem solver SCIP-JACK.
Mathematics and Statistics
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0
Related items
Showing items related by title, author, creator and subject.
-
Rumination-focused cognitive behaviour therapy for residual depression: a case series.
Watkins, E.R; Scott, J; Wingrove, J; et al. (Elsevier, 1 September 2007)The treatment of chronic and recurrent depression is a priority for the development of new interventions. The maintenance of residual symptoms following acute treatment for depression is a risk factor for both chronic ... -
An exploration study of the Kagenfels and Natzwiller granites, Northern Vosges mountains, France: A combined approach of stream sediment geochemistry and automated mineralogy
Steiner, BM; Rollinson, GK; Condron, JM (MDPI, 3 December 2019)Following a regional reconnaissance stream sediment survey that was carried out in the northern Vosges Mountains in 1983, a total of 20 stream sediment samples were collected with the aim of assessing the regional prospectivity ... -
Tools and workflows for Li-Cs-Ta (LCT) pegmatite exploration
Steiner, B (MDPI, 20 August 2019)The increasing demand for green technology and battery metals necessitates a review of geological exploration techniques for Li–Cs–Ta (LCT) pegmatites, which is applicable to the work of mining companies. This paper reviews ...