Reduction techniques for the prize collecting Steiner tree problem and the maximum-weight connected subgraph problem

DOI10.1002/net.21857zbMath1409.90048OpenAlexW2739849971WikidataQ129034108 ScholiaQ129034108MaRDI QIDQ3120785

Daniel Rehfeldt, Stephen J. Maher, Thorsten Koch

Publication date: 19 March 2019

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/129080/1/PcMwReductions_Preprint.pdf

zbMATH Keywords

Steiner tree problemreduction techniquesprize-collecting Steiner tree problemmaximum-weight connected subgraph problemrooted prize-collecting Steiner tree problemSteiner tree reductions

Mathematics Subject Classification ID

Communication networks in operations research (90B18)

Related Items

Imposing Contiguity Constraints in Political Districting Models, On the Exact Solution of Prize-Collecting Steiner Tree Problems, Solving Steiner trees: Recent advances, challenges, and perspectives, Vertex covering with capacitated trees

Uses Software

• SCIP
• SCIP-Jack